Найти дублирующий элемент из целого числа

Question

На прошлой неделе я присутствовал на интервью. Они задали вопрос о поиске дублирующего элемента в целочисленном значении. Я знаю программу с использованием массива, но они спрашивали меня без массива. Помогите мне найти дублирующий элемент в целочисленном массиве без массива.

Вопрос:

Найти дубликат элемента из целого отображения элемента без дублирующего номера. Как I/P: 43456 O/P: 4356. Состояние: не массив не должен использоваться

Coding:

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

я действительно понял вопрос означает, что в качестве ввода следует указать целое число, а не массив целых чисел:

Они задали вопрос о поиске дублирующего элемента в целочисленном значении.

Решение проблемы. В моем исходном решении основная функция была рекурсивной. Эта функция, похоже, сработала, но я не понял, что проблема требует, чтобы дублирующие цифры были взяты из младших цифр. Мое рекурсивное решение сначала удалило цифры более высокого порядка. Это означало, что для введенного ввода образца 43456 оценили до 3456 вместо желаемого 4356.

Я переработал функцию remove_dups(), чтобы удовлетворить это требование. Он больше не рекурсивный. Функция создает новый номер, потребляя входной номер, беря цифру наивысшего порядка и комбинируя ее с цифрой наивысшего порядка оставшихся цифр после удаления дубликатов.

Используются три вспомогательные функции. Функция remove_digits() используется для удаления всех вхождений цифры из числа. Функции и 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 

Update

Код, который я первоначально отправил не обрабатывали отрицательные числа. Это связано с тем, что, когда я первоначально тестировал отрицательные числа, результаты были неверными. В этой сломанной версии я использовал значения long в функциях, за исключением параметров plc, которые были unsigned long. Я ошибочно предположил, что эта проблема связана с оператором модуля, и просто изменила все на unsigned. Казалось, что было бы достаточно просто преобразовать желаемое отрицательное число в положительное, а затем умножить результат на -1. Вот прототипы функций для оригинального, сломанного кода:

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 

Answer 2

Это грубый набросок:

Для каждого целого числа на входе, пройти через вход в направлении начала, и сравнить каждое целое число текущий. Если есть совпадение, переходите к следующему целому числу. Если вы достигнете начала, это не дубликат, поэтому распечатайте его.

void printRepeating(const int arr[], size_t size) { 
    const int* begin = arr; 
    const int* end = arr + size; 
    if (begin == end) return; 
    // First element cannot be a duplicate, so always print it 
    std::cout << *begin; 
    // Traverse input array 
    const int* curr = begin; 
    while (++curr < end) { 
     // Traverse back to find a duplicate 
     const int* curr_rev = curr - 1; 
     for (; curr_rev >= begin && *curr != *curr_rev; --curr_rev); 
     if (curr_rev < begin) 
      // Reached the beginning, so it cannot be a duplicate 
      std::cout << " " << *curr; 
    } 
} 

И хотя я не уверен, является ли строительство указатель на элемент непосредственно перед массивом не определено поведение, здесь небольшое изменение, что пересекает вход спереди назад, чтобы найти дубликат. Это только основной цикл - все остальное, как и выше:

// Traverse input array 
    const int* curr = begin; 
    while (++curr < end) { 
     // Traverse again to find a duplicate 
     const int* cmp = begin; 
     for (; cmp < curr && *cmp != *curr; ++cmp); 
     if (cmp == curr) 
      // Reached current integer, so it cannot be a duplicate 
      std::cout << " " << *curr; 
    } 

Учитывая эту программу:

int main() { 
    const int arr[]{ 1, 2, 3, 1, 3, 6, 6 }; 
    printRepeating(arr, std::end(arr) - std::begin(arr)); 
} 

производит следующий вывод:

1 2 3 6 

Answer 3

Для примера

I/P: 43456 O/P: 4356

1 w чтобы подумать об этом, так это то, что цифра выводится только в том случае, если она не присутствует в более значительной части номера. Таким образом, мы проходим каждую цифру от наименьшего - до самого значительного. Если цифра (lastdig(num)) присутствует в более значительной части номера (butlastdig(num)), мы отбрасываем ее, иначе мы ее сохраняем.

#include <stdbool.h> 
#include <stdio.h> 

inline unsigned lastdig(unsigned n) { return n%10; } 
inline unsigned butlastdig(unsigned n) { return n/10; } 
inline bool is_single_digit(unsigned n) { return n<10; } 

bool is_in(unsigned digit, unsigned num) 
{ 
    if (is_single_digit(num)) 
     return digit==num; 
    else 
     return (digit==lastdig(num)) || is_in(digit, butlastdig(num)); 
} 

unsigned unique(unsigned num) 
{ 
    unsigned last, butlast; 

    if (is_single_digit(num)) 
     return num; 
    last=lastdig(num);   
    butlast=unique(butlastdig(num)); 

    if (is_in(last, butlast)) 
     return butlast; 
    else 
     return butlast*10 + last; 
} 

main(int argc, char **argv) 
{ 
    int i=atoi(argv[1]); 
    if (i < 0) 
     printf("nonnegative numbers only\n"); 
    else 
     printf("%u %u\n", i, unique(i)); 
}