c++ - 从整数中查找重复元素

Question

上周我参加了面试。他们问了一个在整数值中查找重复元素的问题。我知道使用数组的程序，但他们问我没有数组。请帮助我在没有数组的整数中查找重复元素。

问题:

从整数中查找重复元素，显示没有重复数字的元素。如 I/P:43456 O/P:4356。条件:不应使用数组

编码:

void printRepeating(int arr[], int size) {
    int i;
    printf("The repeating elements are: \n");
    for (i = 0; i < size; i++) {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] = -arr[abs(arr[i])]; elseprintf(" %d ", abs(arr[i]));
    }
}
int main() {
    int arr[] = { 1, 2, 3, 1, 3, 6, 6 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    printRepeating(arr, arr_size);
    getchar();
    return 0;
}

Answer 1

我实际上理解这个问题的意思是应该给出一个整数，而不是整数数组作为输入:

They asked a question for finding a duplicate element in integer value.

这是解决此问题的解决方案。在我原来的解决方案中，主要功能是递归的。这个函数似乎有效，但我误解了这个问题要求首先从低位数字中取出重复的数字。我的递归解决方案首先删除了高阶数字。这意味着对于提供的示例输入，43456 计算结果为 3456，而不是所需的 4356。

我重新设计了remove_dups()函数来满足这个要求。它不再是递归的。该函数通过使用输入数字、取出最高位数字并在删除重复项后将其与剩余数字的最高位数字组合来构建新数字。

使用了三个辅助函数。 remove_digits() 函数用于删除数字中所有出现的数字。 get_place() 和 remove_place() 函数用于获取给定位置的数字，其中位置由 1, 10, 100,... 表示，并分别从给定位置删除数字。

以下是 get_place() 函数如何工作的示例:

get_place(1234, 100) --> (1234 % (10 * 100) - 1234 % 100) / 100
                     --> (1234 % 1000 - 1234 % 100) / 100
                     --> (234 - 34) / 100
                     --> 200 / 100
                     --> 2

以及 remove_place() 函数如何工作的示例:

remove_place(1234, 100) --> (1234 / (10 * 100)) * 100 + 1234 % 100
                        --> (1234 / 1000) * 100 + 34
                        --> 1 * 100 + 34
                        --> 100 + 34
                        --> 134

更新

我最初发布的代码不处理负数。这是因为当我最初用负数进行测试时，结果是不正确的。在这个损坏的版本中，我在函数中使用了 long 值，但 plc 参数除外，这些参数是 unsigned long。我错误地认为这个问题与模运算符有关，只是将所有内容更改为无符号。看起来很简单，只需将所需的负数转换为正数，然后将结果乘以 -1。以下是原始的、损坏的代码的函数原型(prototype):

long get_place(long num, unsigned long plc);
long remove_place(long num, unsigned long plc);
long remove_digits(long num, long d);
long remove_dups(long num);

但进一步考虑发现，最初的问题是 unsigned long 值无法转换为 long 值，因为存在 unsigned long 值不能表示为 long 值。这导致 get_place() 和 remove_place() 函数中出现一些垃圾结果。将所有内容更改为 unsigned long 解决了这个问题，但代价是排除负输入值。但是，随着对问题有了更好的理解，我将所有函数参数和返回值更改为 long 类型。这解决了问题，并允许正确处理负输入值。

这是代码:

#include <stdio.h>

long get_place(long num, long plc);
long remove_place(long num, long plc);
long remove_digits(long num, long d);
long remove_dups(long num);

int main(void)
{
    long number;

    printf("Enter a number (q to quit): ");
    while (scanf("%ld", &number) == 1) {
        printf("%ld\n", remove_dups(number));
        printf("Enter a number (q to quit): ");
    }

    return 0;
}

/* return digit at plc = 1, 10, 100, ... */
long get_place(long num, long plc)
{
    return (num % ( 10 * plc) - num % plc) / plc;
}

/* remove digit at plc = 1, 10, 100, ..., and return result */
long remove_place(long num, long plc)
{
    return (num / (10 * plc)) * plc + num % plc;
}

/* remove all occurrences of d in num and return result */
long remove_digits(long num, long d)
{
    long place = 1;
    while (num / place) {
        if (get_place(num, place) == d)
            num = remove_place(num, place);
        else
            place *= 10;
    }

    return num;
}

long remove_dups(long num)
{
    long result, next_digit;
    long last_place = 1;

    result = 0;
    while (num) {
        for(last_place = 1; (num / (10 * last_place)); last_place *= 10)
            continue;

        next_digit = get_place(num, last_place);
        result = result * 10 + next_digit;
        num = remove_digits((num % last_place), next_digit);
    }
    return result;
}

这是一些示例输出:

Enter a number (q to quit): -43456
-4356
Enter a number (q to quit): 43456
4356
Enter a number (q to quit): -12321
-123
Enter a number (q to quit): 299792458
297458
Enter a number (q to quit): 0
0
Enter a number (q to quit): 1
1
Enter a number (q to quit): -1
-1
Enter a number (q to quit): q