Алгоритм поиска повторяющихся чисел в массиве --- Самый быстрый способ

Question

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

Например: если массив равен {2,3,4,5,2,4,6,2,4,7,3,8,2}

Я должен знать, что есть четыре 2, два 3 и три 4.

Answer 1

вот версия C, которая делает это со стандартным вводом; это так же быстро, как длина ввода (будьте осторожны, количество параметров в командной строке ограничено ...), но должно дать вам представление о том, как действовать:

#include <stdio.h>

int main ( int argc, char **argv ) {
    int dups[10] = { 0 };
    int i;

    for ( i = 1 ; i < argc ; i++ ) 
        dups[atoi(argv[i])]++;

    for ( i = 0 ; i < 10 ; i++ )
        printf("%d: %d\n", i, dups[i]);

    return 0;
}

пример использования:

    $ gcc -o dups dups.c

    $ ./dups 0 0 3 4 5
0: 2
1: 0
2: 0
3: 1
4: 1
5: 1
6: 0
7: 0
8: 0
9: 0

предостережения:

• если вы планируете посчитать также число 10 с, 11 с и т. Д. -> массив dups [] должен быть больше

• оставлено в качестве упражнения для реализации чтения из массива целых чисел и определения их положения

Answer 2

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

Примерно так (в псевдокоде). Вы найдете множество реализаций хэш-карт для C, прибегнув к помощи .

 hash_map = create_new_hash_map()
 for item in array {
   if hash_map.contains_key(item){
      counter = hash_map.get(item)
   } else {
      counter = 0
   }
   counter = counter + 1
   hash_map.put(item, counter)
 }

Answer 3

Это можно решить элегантно, используя Linq:

public static void Main(string[] args)
{
    List<int> list = new List<int> { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };

    var grouping = list
        .GroupBy(x => x)
        .Select(x => new { Item = x.Key, Count = x.Count()});

    foreach (var item in grouping)
        Console.WriteLine("Item {0} has count {1}", item.Item, item.Count);
}

Внутренне он, вероятно, использует хеширование для разбиения списка, но код скрывает внутренние детали - здесь мы только сообщаем ему , что рассчитать. Компилятор / среда выполнения могут свободно выбирать как для его вычисления и оптимизировать по своему усмотрению. Благодаря Linq этот же код будет эффективно выполняться независимо от того, будет ли список запущен в памяти или если список находится в базе данных. В реальном коде вы должны использовать это, но я думаю, вы хотите знать, как это работает внутри.

Более императивный подход, который демонстрирует фактический алгоритм, следующий:

    List<int> list = new List<int> { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (int item in list)
    {
        if (!counts.ContainsKey(item))
        {
            counts[item] = 1;
        }
        else
        {
            counts[item]++;
        }
    }

    foreach (KeyValuePair<int, int> item in counts)
        Console.WriteLine("Item {0} has count {1}", item.Key, item.Value);

Здесь вы можете видеть, что мы перебираем список только один раз, сохраняя счет для каждого элемента, который мы видим в пути. Это было бы плохой идеей, если бы элементы были в базе данных, поэтому для реального кода предпочтительнее использовать метод Linq.

Answer 4

Чем больше вы расскажете нам о входных массивах, тем быстрее мы сможем сделать алгоритм. Например, для вашего примера однозначных чисел создание массива из 10 элементов (с индексом 0: 9) и накопление количества вхождений числа в правом элементе массива (плохо сформулированное объяснение, но вы, вероятно, уловили мой дрейф): скорее всего будет быстрее, чем хеширование. (Я говорю, вероятно, будет быстрее, потому что я не делал никаких измерений и не буду).

Я согласен с большинством респондентов, что хеширование, вероятно, является правильным подходом для самого общего случая, но всегда стоит задуматься о том, является ли ваш случай особенным.

Answer 5

Если вы знаете нижнюю и верхнюю границы, и они не слишком далеко друг от друга, это было бы хорошим местом для использования Radix Sort . Так как это пахнет домашней работой, я оставляю это на ОП, чтобы прочитать статью и реализовать алгоритм.

Answer 6

Вы можете использовать хеш-таблицы для хранения каждого значения элемента в качестве ключа. Затем увеличивайте +1 каждый раз, когда ключ уже существует.

Answer 7

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

Answer 8

Если вы не хотите использовать хеш-таблицу или что-то в этом роде, просто отсортируйте массив и посчитайте количество вхождений, что-то вроде ниже должно работать

    Arrays.sort(array);
    lastOne=array's first element;
    count=0,
    for(i=0; i <array's length; i++)
    {
        if(array[i]==lastOne)
            increment count
        else        
            print(array[i] + " has " + count + " occurrences");
            lastOne=array[i+1];
    }

Answer 9

Вот еще одно решение, но оно требует времени O (nlogn). Используйте подход Divide and Conquer для сортировки заданного массива с помощью сортировки слиянием. На этапе объединения в сортировке слиянием найдите дубликаты, сравнив элементы в двух отсортированных подмассивах.

Answer 10

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