c - 如何删除数字中的特定位数以使获得的数字最小？

Question

如何删除数字中的特定位数以使获得的数字最小？

具体来说，我想编写一个函数int remove_digits(int large, int num_digits_to_remove)：

1. 任何num_digits_to_remove数字都被删除，large就像从其字符串表示中删除字符一样
2. 返回的数字具有从步骤 1 中删除数字的最低可能值

例如，从中删除 4 位数字69469813将给出4613

我更喜欢用 C 写的答案。

Answer 1

主意：

char number[] = "69469813";
char digits[ARRAY_SIZE(number)];
size_t i;

// sort digits; complexity O(n * log n);
sort_digits(digits, number);   // -> digits becomes "99866431"

for (i = 0; i < number_of_digits_to_be_removed; ++i) {
     size_t j;
     for (j = 0; j < ARRAY_SIZE(number); ++j) {
         if (number[j] == digits[i]) {
             number[j] = 'X';      // invalidate it
             break;
         }
     }
 }

 for (i = 0; i < ARRAY_SIZE(number); ++i)
     if (number[i] != 'X')
         printf("%c", number[i]);

整个事物的复杂度为 O(n * m)；

Answer 2

基本思想是，如果只能删除一个数字，则要删除第一个数字（从最高有效数字开始），然后是较小的数字。

例如，如果你的号码是 123432，你想去掉 4（因为它后面跟着一个 3），得到 12332。

然后，您对要删除的数字重复此过程：

char *num = "69469813";
char *buf = malloc(strlen(num)+1);
size_t to_remove = 4;

while (to_remove --> 0) {
    char *src = num;
    char *dst = buf;

    while (*src < *(src+1)) { *dst++ = *src++; } // Advance until the next digit is less than the current digit
    src++;                                       // Skip it
    while (*dst++ = *src++);                     // Copy the rest

    strcpy(num, buf);
}
printf("%s\n", num); // Prints 4613

Answer 3

我不知道C，但这是我在java中的做法：

String original = "69469813";
String result = "";

int numNeedToBeTaken = 4;
int numLeft = original.length() - numNeedToBeTaken;

while(result.length() < numLeft)
{
    String temp = original.substring(0,original.length()-numNeedToBeTaken+1);
    int smallest= 9;
    int index = 0;
    for(int i = 0; i<temp.length(); i++)
    {
        int number = Integer.parseInt(Character.toString(temp.charAt(i)));
        if( number < smallest)
        {
            smallest = number;
            index = i+1;
        }
    }
    numNeedToBeTaken--;
    result = result.concat(String.valueOf(smallest));
    original = original.substring(index);
}
Log.d("debug","result: "+result); //tested to work with your example, returns 4613

将其转换为 C 应该很容易，我只使用了一些基本操作。