Удалить дубликаты из большого несортированного массива и поддерживать порядок - PullRequest
Новая
       15

Удалить дубликаты из большого несортированного массива и поддерживать порядок

0 голосов
/ 14 сентября 2018

У меня есть несортированный массив целых чисел, значение которого варьируется от Integer.MIN_VALUE до Integer.MAX_VALUE. В массиве может быть несколько дубликатов любого целого числа. Мне нужно вернуть массив со всеми удаленными дубликатами, а также поддерживать порядок элементов.

пример: 

int[] input = {7,8,7,1,9,0,9,1,2,8}

вывод должен быть {7,8,1,9,0,2}

Я знаю, что эту проблему можно решить с помощью LinkedHashSet, но мне нужно решение, которое не требует значительного буферного пространства.

Ответы [ 5 ]

0 голосов
/ 14 сентября 2018

Я попробовал несколько подходов - используя Map и Set, чтобы получить различные элементы.Согласно требованию эти не используют LinkedHashSet или LinkedHashMap.Кроме того, порядок сохраняется.

Я использовал этот пример входного массива в обоих случаях и получил ожидаемый результат.
ВХОД: int [] arr = new int [] {1, 99, 2, 82, 99, -20, 9, 2, 9, 45, -319, 1};
РЕЗУЛЬТАТ: [1, 99, 2, 82, -20, 9, 45, -319]

Примеры кода:

Использование карты : 

int [] arrayWithDistictElements = new int [arr.length];
int noOfDistinctElements = 0;
HashMap<Integer, Integer> map = new HashMap<>();

for (int i = 0, j = 0; i < arr.length; i++) {

    if (map.put(arr [i], 1) == null) {

        arrayWithDistictElements [j++] = arr [i];
        ++noOfDistinctElements;
    }
}

int [] result = Arrays.copyOf(arrayWithDistictElements, noOfDistinctElements);


Использование набора : 

Set<Integer> set = new HashSet<>();
int [] arrayWithDistictElements = new int [arr.length];
int noOfDistinctElements = 0;

for (int i = 0, j = 0; i < arr.length; i++) {

    if (set.add(arr [i])) {

        arrayWithDistictElements [j++] = arr [i];
        ++noOfDistinctElements;
    }
}

int [] result = Arrays.copyOf(arrayWithDistictElements, noOfDistinctElements);


Код :

Вот полный код моих тестов Iпробовал и некоторые результаты: 

import java.util.*;
import java.util.stream.*;
import java.time.*;
import java.text.*;
public class UniqueArrayTester {

    private final static int ARRAY_SIZE = 10_000_000;
    private static Random r = new Random();

    public static void main(String [] args) {

        DecimalFormat formatter = new DecimalFormat("###,###,###,###");
        System.out.println("Input array size: " + formatter.format(ARRAY_SIZE));

        for (int i = 0; i < 5; i++) {

            // For testing with a small input and print the result use this as input:
            //int [] arr = new int [] {1, 99, 2, 82, 99, -20, 9, 2, 9, 45, -319, 1};
            //System.out.println(Arrays.toString(arr));

            System.out.println("[Test " + Integer.toString(i+1) + "]");
            int [] arr = getArray();
            process1(arr);
            process2(arr);
            process3(arr);
        }
    }

    private static int [] getArray() {  
        return IntStream.generate(() -> r.nextInt())
                        .limit(ARRAY_SIZE)
                        .toArray();
    }

    /*
     * Process uses Stream API.
     */
    private static void process1(int [] arr) {
        LocalTime time1 = LocalTime.now();
        int [] result = IntStream.of(arr).distinct().toArray();
        LocalTime time2 = LocalTime.now();
        System.out.println("Process 1 (using streams) out array size: " + result.length);
        System.out.println("    Duration in millis: " + Duration.between(time1, time2).toMillis());
        //System.out.println(Arrays.toString(result));
    }

    /*
     * Process uses a Map to arrive at distinct elements.
     */ 
    private static void process2(int [] arr) {
        LocalTime time1 = LocalTime.now();
        int [] arrayWithDistictElements = new int [arr.length];
        int noOfDistinctElements = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < arr.length; i++) {
            if (map.put(arr [i], 1) == null) {
                arrayWithDistictElements [j++] = arr [i];
                ++noOfDistinctElements;
            }
        }
        int [] result = Arrays.copyOf(arrayWithDistictElements, noOfDistinctElements);
        LocalTime time2 = LocalTime.now();
        System.out.println("Process 2 (using map) out array size: " + result.length);
        System.out.println("    Duration in millis: " + Duration.between(time1, time2).toMillis());
        //System.out.println(Arrays.toString(result));
    }

    /*
     * Process uses a Set to arrive at distinct elements.
     */ 
    private static void process3(int [] arr) {
        LocalTime time1 = LocalTime.now();
        Set<Integer> set = new HashSet<>();
        int [] arrayWithDistictElements = new int [arr.length];
        int noOfDistinctElements = 0;
        for (int i = 0, j = 0; i < arr.length; i++) {
            if (set.add(arr [i])) {
                arrayWithDistictElements [j++] = arr [i];
                ++noOfDistinctElements;
            }
        }
        int [] result = Arrays.copyOf(arrayWithDistictElements, noOfDistinctElements);
        LocalTime time2 = LocalTime.now();
        System.out.println("Process 3 (using set) out array size: " + result.length);
        System.out.println("    Duration in millis: " + Duration.between(time1, time2).toMillis());
        //System.out.println(Arrays.toString(result));
    }
}


Результаты теста :

Используемое оборудование: процессор Intel CORE i3, Windows 7 64 бит, Java 8 

Input array size: 10,000,000
[Test 1]
Process 1 (using streams) out array size: 9988498
    Duration in millis: 10649
Process 2 (using map) out array size: 9988498
    Duration in millis: 10294
Process 3 (using set) out array size: 9988498
    Duration in millis: 8982
[Test 2]
Process 1 (using streams) out array size: 9988331
    Duration in millis: 7839
Process 2 (using map) out array size: 9988331
    Duration in millis: 5567
Process 3 (using set) out array size: 9988331
    Duration in millis: 4155
[Test 3]
Process 1 (using streams) out array size: 9988286
    Duration in millis: 9138
Process 2 (using map) out array size: 9988286
    Duration in millis: 6799
Process 3 (using set) out array size: 9988286
    Duration in millis: 7155
[Test 4]
Process 1 (using streams) out array size: 9988431
    Duration in millis: 7908
Process 2 (using map) out array size: 9988431
    Duration in millis: 6909
Process 3 (using set) out array size: 9988431
    Duration in millis: 7205
[Test 5]
Process 1 (using streams) out array size: 9988334
    Duration in millis: 7971
Process 2 (using map) out array size: 9988334
    Duration in millis: 6910
Process 3 (using set) out array size: 9988334
    Duration in millis: 7196
0 голосов
/ 14 сентября 2018

Вы можете использовать HashSet вместо LinkedHashSet, но при этом все равно используется буфер: 

 private static int[] noDups(int[] arr) {
    Set<Integer> set = new HashSet<>();
    int nextIndex = 0;
    for (int i = 0; i < arr.length; ++i) {
        if (set.add(arr[i])) {
            arr[nextIndex++] = arr[i];
        }

    }

    return Arrays.copyOfRange(arr, 0, nextIndex);
}

Просто обратите внимание, что это меняет исходный массив, если вы не хотите, чтобы потребовался другой вызов для создания копии: int[] copy = Arrays.copyOfRange(arr, 0, arr.length);

В противном случае, если вы хотите сделать это на месте, без какого-либо дополнительного буфера, вам придется перебирать массив во вложенном массиве через, и сложность составит: O(n*n), что довольно плохо .

0 голосов
/ 14 сентября 2018

Один умный подход - использовать LinkedHashSet для представления входного массива. LinkedHashSet обладает свойствами, которые поддерживает порядок вставки (поведение связанного списка), но также игнорирует тот же ключ, который вставляется снова (поведение карты). Это означает, что, например, значение 7 будет вставлено в список / карту только один раз, при первом появлении. Это поведение, которое мы хотим. 

LinkedHashSet<Integer> lhs = new LinkedHashSet<>();
int[] input = new int[] {7, 8, 7, 1, 9, 0, 9, 1, 2, 8};
for (int val : input) lhs.add(val);
int[] output = new int[lhs.size()];
int i = 0;
for (Integer val : lhs) {
    output[i++] = val;
}
System.out.println(Arrays.toString(output));

[7, 8, 1, 9, 0, 2]

Демо

0 голосов
/ 14 сентября 2018

Вы можете использовать java 8 Arrays stream.distinct() метод для получения различных значений из массива, и он останется только в порядке ввода 

public static void main(String[] args) {
    int[] input = {7,8,7,1,9,0,9,1,2,8};
    int[] output = Arrays.stream(input).distinct().toArray();
    System.out.println(Arrays.toString(output)); //[7, 8, 1, 9, 0, 2]
}
0 голосов
/ 14 сентября 2018

Как насчет того, чтобы сделать это прямо так 

    int[] input =  {7,8,7,1,9,0,9,1,2,8};
    ArrayList<Integer> list = new ArrayList<>();
    for(int i = 0;i<input.length;i++)
    {
        if(!list.contains(input[i]))
        {
            list.add(i);
        }
    }
    int[] output = new int[list.size()];
    for(int i = 0;i<list.size();i++)
    {
        output[i] = list.get(i);
    }
...