Удалить дубликаты из большого целочисленного массива с помощью Java

Ответ 1

Возможно, вы можете использовать бит-набор? Я не знаю, насколько эффективен Java BitSet. Но 9999999 возможных значений будет принимать только 9999999/8 = 1250000 bytes = чуть более 1Mb. Когда вы проходите массив значений, установите соответствующий бит в значение true. Затем вы можете пройти через бит и вывести соответствующее значение всякий раз, когда бит бит установлен в true.

1Mb будет входить в кеш процессора, поэтому это может быть довольно эффективным в зависимости от реализации набора бит.

Это также имеет побочный эффект для сортировки данных.

И... это алгоритм O (n), так как он требует одного прохода над входными данными, заданными операциями являются O (1) (для набора на основе массива, подобного этому), а выходной проход - также O (m), где m - количество уникальных значений и, по определению, должно быть <= n.

Ответ 2

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

Ответ 3

Set<Integer> set = new HashSet<Integer>();
Collections.addAll(set, array);

вам нужен массив Integer[] вместо int[].

Ответ 4

Сначала попробуйте отсортировать массив:

int arr[] = yourarray;
Arrays.sort(arr);
// then iterate arr and remove duplicates

Ответ 5

int[] a;
Arrays.sort(a);
int j = 0;
for (int i = 1; i < a.length; ++i) {
  if (a[i] != a[j]) {
    ++j;
    a[j] = a[i];
  }
}
// now store the elements from 0 to j (inclusive - i think)

Ответ 6

Истинно отчаянный может записать массив на диск и отключить sort | uniq | wc -l <infile.txt и захватить вывод. Это было бы необходимо, если бы память была еще слишком плотной или объемное пространство целых чисел стало больше. Мне это не нравится (он даже работает unix!), Но я хочу сказать, что есть много способов выполнить задачу.

Другое наблюдение заключается в том, что минимальное значение составляет 100 000. Таким образом, мы могли бы вычесть 100 000 из максимального значения 9999,999, уменьшив пространство в пространстве и, таким образом, сохранив некоторую память. Возможно, 100k/8 бит - это арахис в схеме вещей, но он по существу свободен для этого.

Ответ 7

Возможно, вы могли бы сделать несколько проходов над данными? Например, если вы сделали десять проходов над данными и применили одно из приведенных выше предложений к меньшему подмножеству данных (скажем, когда значение mod pass # == 0). Таким образом:

for (int i = 0 to 9) {
  set = new Set()
  for (each entry in the data set) {
    if (entry % i == 0) {
      set.add(entry)
    }
  }
  output set
}

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

Ответ 8

Может быть, хеш-набор, который работает с примитивами, а не объекты, выполнит эту работу? Существуют бесплатные реализации (ранее они не использовались, но, возможно, это работает):

http://trove4j.sourceforge.net/

http://trove4j.sourceforge.net/javadocs/gnu/trove/TIntHashSet.html

Тогда будет выглядеть:

int[] newArray = new TIntHashSet(yourArray).toArray();

Ответ 9

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

    final int MAX = 100; 
    int[] arrayWithRepeats = {99, 0, 10, 99, 0, 11, 99};

    //we are counting here integers with the same value
    int [] arrayOfValues = new int[MAX+1];
    int countOfUniqueIntegers = 0;
    for(int i : arrayWithRepeats) {
        if(arrayOfValues[i] == 0) {
            countOfUniqueIntegers++;
        }
        arrayOfValues[i]++;
    }

    // you can use arrayOfValues (smaller) or convert it
    // to table of unique values (more usable)

    int[] arrayOfUniqueValues = new int[countOfUniqueIntegers];
    int index = 0;
    for(int i = 0; i<arrayOfValues.length; i++) {
        if(arrayOfValues[i] != 0) {
            arrayOfUniqueValues[index] = i;
            index++;
        }
    }

    //and now arrayOfUniqueValues is even sorted
    System.out.println( Arrays.toString(arrayOfUniqueValues) );

Выход: [0, 10, 11, 99]