贪心算法解决删数问题) 有一个长度为n的正整数,从中取出k(k < n)个数,使剩余的数保持原来的次序不变,求这个正整数经过删数之后最小是多少(如n=178543,k=4
时间: 2024-02-13 15:02:03 浏览: 95
这是一个经典的贪心算法问题,可以使用贪心算法来解决。
具体做法如下:
1. 从左到右扫描这个正整数,如果当前数字比后面的数字大,则删除当前数字,直到删除k个数字为止。
2. 如果删除的数字不足k个,说明当前数字递增,从右往左扫描,删除后面的数字,直到删除k个数字为止。
3. 删除后,将剩下的数字连接起来,得到的就是最小的正整数。
例如,对于n=178543,k=4,按照上述贪心算法,可以得到最小的正整数为1343。
实现代码如下(使用Python语言):
```
def delete_number(n, k):
stack = []
for i in range(len(n)):
while stack and k > 0 and stack[-1] > n[i]:
stack.pop()
k -= 1
stack.append(n[i])
while k > 0:
stack.pop()
k -= 1
return int(''.join(stack))
n = '178543'
k = 4
print(delete_number(n, k)) # 输出结果为1343
```
阅读全文