从输入数字中删除k个数字后如何获得最少的数字

例如，如果输入的数字是24635 ，则在删除任何3位数后，最小数字是23 。

它与取两个最小的数字不同，因为必须保持数字的顺序。

Answer 1

删除k数字意味着保持n - k数字，其中n是总的位数。

使用您按升序排序的堆栈。 只要你仍然可以使它成为n - k数字并且当前元素小于堆栈顶部，你可以从中删除元素：

 push(2) => 2 push(4) because 2 < 4 => 24 push(6) because 4 < 6 => 246 pop() because 3 < 6 and we can still end up with 2 digits => 24 pop() for the same reason => 2 push(3) => 23 push(5) => 235 

然后只取第一个k数=> 23 。 或者你可以确保永远不要超过k位数，然后最后的堆栈是你的解决方案。

请注意，如果这意味着您将无法构建k位数的解，则无法弹出元素。 为此，您需要检查堆栈中当前的元素数以及输入数字上当前位置右侧的位数。

伪代码：

 stack = [] for each d in digits: while !stack.empty() and d < stack.top() and (*): stack.pop() if stack.size() < n - k: stack.push(d) (*) - exercise, fill in the condition that prevents you from popping elements if you still want to be able to get to a solution. Hint: count how many elements the for loop went over already and see how many are left. Also consider how many you have left in the stack. 

由于每个元素最多进入和离开堆栈一次，因此复杂度为O(n) 。

Answer 2

提供递归方法。

在每次迭代测试中成功k == 0 …
或者失败num == 0因为没有剩下要删除的数字。
（返回10比返回num其他路径更差）

否则以两种方式递归：
1）保持最低有效位数并尝试使用高位数字。
2）删除最低位数并尝试使用高位数字， k--
返回更好的一个。

 unsigned reduce(unsigned num, unsigned k) { if (k <= 0) { return num; // Success } if (num == 0) { return 10; // Fail } unsigned path1 = reduce(num/10, k)*10 + num%10; unsigned path2 = reduce(num/10, k-1); return path1 < path2 ? path1 : path2; } int main(void) { printf("%u\n", reduce(246, 2)); printf("%u\n", reduce(24635, 3)); printf("%u\n", reduce(53642, 3)); printf("%u\n", reduce(21, 1)); } 2 23 32 1 

此解决方案不依赖于知道位数，只需要知道删除所需的数量。

Answer 3

很简单的解决方案

我们有n数字，我们必须删除它们中的k才能离开nk 。 我们可以很容易地确定第一个数字是什么。

最后的nk-1数字显然不能是答案的第一个数字，只有在没有足够数字后才能生成足够长的数字。

因此，我们简单地忽略最后的nk数字，并且关注前k数字并找到该k数字集合中的最小数字。 这将是我们答案的第一位数字。 例如，无论X是什么，所有三位数字5XX都小于6XXforms的所有数字。 （如果存在平局，两位数分享最小的荣誉，则选择左侧的数字，因为它可以在以后为您提供更大的灵活性。）

现在你知道第一个数字是什么，你可以忽略它和左边的一切，并用剩余的数字递归地重复整个事情 – 我可以用剩余数字做出的最小数字是多少？

Answer 4

我认为这样可以解决问题：

让我们使用532874902352.如果您愿意，可以尝试任何您想要的东西。

使用532874902352，我们将删除4位数，或任何您想要的数字。

移动4 + 1位数53287|4902352

找到最小的数字。 2

删除所选数字之前的所有数字。 我们现在有28749023532; 我们删除了2位数。 还有2个。

在第一个之后删除2位数。 我们有249023532.我们去。

但是，如果要删除的数字是倒数第二个，则删除最后一个，如果它大于倒数第二个。

例子：

24635，删除3。

移入3 + 1。

2463 | 5

删除所有2之前的最小值。

24635

删除以满足所需的位数，但是删除5而不是3。

23

43331，删除3。

移入3 + 1。

4333 | 1

删除所有3之前，最小的。

31

删除以满足所需的位数，3。我们没有更多的数字要删除。

由您来实现此方法。

Answer 5

知道你想要保持数字顺序肯定会使这个解决方案更加困难。

我同意IVlad ， char[] s不是要走的路。

我认为这是一个相当不错的解决方案：

 #include  #include  #include  #define DIGITS_TO_REMOVE 3 // Assumed to be positive int recurse(int* foo, int begin, int end, int previous, int max){ int i; int min = begin; for (i = begin; i <= end; ++i){ if (foo[min] > foo[i]){ min = i; } } return previous * pow(10, max - end + 1) + (max > end ? recurse(foo, min + 1, end + 1, foo[min], max) : foo[min]); } int main(void) { int foo[(const int)ceil(log10(INT_MAX))]; int bar = 24635; // Assumed to be larger than pow(10, DIGITS_TO_REMOVE) - 1 int size = ceil(log10(bar)); int i; int min = size - DIGITS_TO_REMOVE; for (i = 1; bar > 0; bar /= 10, ++i){ foo[size - i] = bar % 10; if (i >= DIGITS_TO_REMOVE && foo[size - i] <= foo[min]){ min = size - i; } } printf("%d", recurse(foo, min + 1, DIGITS_TO_REMOVE + 1, foo[min], size - 1)); return 0; } 

编辑：

IVlad还建议我使解决方案返回一个数组而不仅仅是一个int因此它不会被约束到返回类型的大小。 显然有一些工作需要用于准备输入和输出数组，这可能不是OP的目标，但这是一个有趣的问题。

 #include  #define DIGITS_TO_REMOVE 3 // Assumed to be positive #define INPUT_SIZE 5 // Assumed to be greater than DIGITS_TO_REMOVE void recurse(int* input, int* output, int begin, int end){ int i; int min = begin; for (i = begin; i < end; ++i){ if (input[min] > input[i]){ min = i; } } output[end - DIGITS_TO_REMOVE - 1] = input[min]; if (end < INPUT_SIZE){ recurse(input, output, min + 1, end + 1); } } int main(void) { int foo[] = { 2, 4, 6, 3, 5 }; int bar[INPUT_SIZE - DIGITS_TO_REMOVE]; int i; recurse(foo, bar, 0, DIGITS_TO_REMOVE + 1); for (int i = 0; i < INPUT_SIZE - DIGITS_TO_REMOVE; ++i){ printf("%d", bar[i]); } return 0; } 

Answer 6

 private static int getLeastNumberAfterDelete(int num, int dighitsDel) { String s = ""; char[] charArray = String.valueOf(num).toCharArray(); Arrays.sort(charArray); // Sort charArray for (int i = 0; i < (charArray.length - dighitsDel); i++) { s += charArray[i];//concatenate } return Integer.valueOf(s); } 

Answer 7

非常简单的算法让我想到了

1. 将输入编号视为字符串
2. 从数字9开始向后循环到0
3. 检查9是否存在给定的数字（在java中我们可以使用indexOf() ），如果存在则删除。 检查删除的数字的数量是否等于删除的输入数字的数量。 如果没有，检查9存在gaain直到它不存在（ indexOf()将在java下返回-1）以查看是否重复相同的数字。 现在重复，如果是8，直到预期没有数字被删除
4. 到目前为止我们已经删除了数字，这可能会导致更大的数字
5. 现在从0到9循环并检查数字中是否存在数字中的每个数字，并按升序重新排列

例如 ：-

给定数字是24635 ，没有要删除的数字是2

1. 从9开始，你发现要删除的第一个数字是6然后是5
2. 剩下的数字是243
3. 从0到9的开始循环按升序重新排列它，如234

Answer 8

这个想法是基于这样一个事实，即第一个（n + 1）个字符中的字符必须存在于结果数中。 因此，我们选择最小的第一个（n + 1）数字并将其放入结果中，并重复剩余的字符。 下面是完整的算法。

将结果初始化为空字符串，即res =“”

buildLowestNumber（str，n，res）

1）如果n == 0，那么没有什么可以删除。 将整个’str’附加到’res’并返回

2）让’len’为’str’的长度。 如果’len’小于或等于n，则可以删除所有内容。 不附加任何’res’并返回

3）找到’str’的第一个（n + 1）个字符中的最小字符。 让最小字符的索引为minIndex。 将’str [minIndex]’附加到’res’并在minIndex和n = n-minIndex之后重复出现子串

buildLowestNumber（str [minIndex + 1..len-1]，n-minIndex）。

 #include using namespace std; // A recursive function that removes 'n' characters from 'str' // to store the smallest possible number in 'res' void buildLowestNumberRec(string str, int n, string &res) { // If there are 0 characters to remove from str, // append everything to result if (n == 0) { res.append(str); return; } int len = str.length(); // If there are more characters to remove than string // length, then append nothing to result if (len <= n) return; // Find the smallest character among first (n+1) characters // of str. int minIndex = 0; for (int i = 1; i<=n ; i++) if (str[i] < str[minIndex]) minIndex = i; // Append the smallest character to result res.push_back(str[minIndex]); // substring starting from minIndex+1 to str.length() - 1. string new_str = str.substr(minIndex+1, len-minIndex); // Recur for the above substring and n equals to n-minIndex buildLowestNumberRec(new_str, n-minIndex, res); } // A wrapper over buildLowestNumberRec() string buildLowestNumber(string str, int n) { string res = ""; // Note that result is passed by reference buildLowestNumberRec(str, n, res); return res; } // Driver program to test above function int main() { string str = "121198"; int n = 2; cout << buildLowestNumber(str, n); return 0; } 

Answer 9

 #include  #include  #include  #include  #include  #include  #include  #include  #define mod 1000000007 #define ll long long using namespace std; bool Compare (pair p1, pair p2) { if (p1.first < p2.first) { return true; } return false; } int main() { priority_queue , vector  >, function, pair ) > > pq (Compare); int n, k; cin>>n>>k; int i = 1; while (n) { pq.push(make_pair(n%10, i)); n = n/10; i++; } for(int j =1; j<=k;j++){ pq.pop(); } int number = pq.top().first; int index = pq.top().second; int digit = 1; pq.pop(); while(!pq.empty()){ int current_index = pq.top().second; digit = digit * 10; if(current_index < index) { number = number * 10 + pq.top().first; } else { number = digit * pq.top().first + number; } pq.pop(); } cout< 

我使用priority_queue和pair解决了这个问题。 如果有更好的解决方案，请告诉我