使用Java实现给定一个正整数,去掉其中的k位数,剩下的数字按原先次序排列,如何让生成的数最小。
时间: 2023-05-24 21:06:18 浏览: 209
删数问题给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个
4星 · 用户满意度95%
算法思路:
首先我们可以观察到一个结论,即要想让生成的数最小,就应当尽可能让高位的数小,因为高位数的权值更高。而为了让高位数最小,我们需要尽可能地保留低位数,因为低位数的权值越小。
所以,我们可以使用贪心算法来解决这个问题,具体思路如下:
- 从左往右遍历原数中的每个数字,依次将它们加入到生成的新数中。
- 对于当前加入到新数中的数字,如果它比前面已经加入到新数中的数字大,那么就应当将前面的数字删除掉,直到新数中前面的数字都小于等于当前数字,或者已经删掉了k个数字(因为只能删掉k个数字)。
- 如果已经删掉了k个数字,就将当前数字都加入到新数中,剩下的数字全部舍弃。
- 如果遍历完整个原数,新数中依然没有k位数字,就从后往前,将原数中剩下的数字依次加入到新数中,直到新数中的位数为k为止。
在实现上,我们可以使用一个栈来保存新数中已加入的数字,这样在进行数字删除时,只需要将栈中的数字弹出即可。栈中的数字按照由小到大的顺序排列,这样在加入新数字时,比栈顶数字小的数字就可以直接加入,因为它们肯定已经在新数的前面了。
阅读全文