How to efficiently remove duplicates from an array without using Set

Меня попросили написать собственную реализацию для удаления дублированных значений в массиве. Вот что я создал. Но после тестов с 1 000 000 элементов на завершение ушло очень много времени. Могу ли я что-нибудь сделать для улучшения своего алгоритма или устранить какие-либо ошибки?

Мне нужно написать свою собственную реализацию - не использовать Set, HashSet и т.д. Или любые другие инструменты, такие как итераторы. Просто массив для удаления дубликатов.

public static int[] removeDuplicates(int[] arr) {

    int end = arr.length;

    for (int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            if (arr[i] == arr[j]) {                  
                int shiftLeft = j;
                for (int k = j+1; k < end; k++, shiftLeft++) {
                    arr[shiftLeft] = arr[k];
                }
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }
    return whitelist;
}

вы можете воспользоваться помощью коллекции Set

int end = arr.length;
Set<Integer> set = new HashSet<Integer>();

for(int i = 0; i < end; i++){
  set.add(arr[i]);
}

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

Iterator it = set.iterator();
while(it.hasNext()) {
  System.out.println(it.next());
}

Разрешено ли вам использовать потоки Java 8:

Arrays.stream(arr).distinct().toArray();

Примечание: Я предполагаю, что массив отсортирован.

Код:

int[] input = new int[]{1, 1, 3, 7, 7, 8, 9, 9, 9, 10};
int current = input[0];
boolean found = false;

for (int i = 0; i < input.length; i++) {
    if (current == input[i] && !found) {
        found = true;
    } else if (current != input[i]) {
        System.out.print(" " + current);
        current = input[i];
        found = false;
    }
}
System.out.print(" " + current);

вывод:

  1 3 7 8 9 10

Небольшая модификация самого исходного кода путем удаления самого внутреннего цикла for .

public static int[] removeDuplicates(int[] arr){
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        for (int j = i + 1; j < end; j++) {
            if (arr[i] == arr[j]) {                  
                /*int shiftLeft = j;
                for (int k = j+1; k < end; k++, shiftLeft++) {
                    arr[shiftLeft] = arr[k];
                }*/
                arr[j] = arr[end-1];
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    /*for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }*/
    System.arraycopy(arr, 0, whitelist, 0, end);
    return whitelist;
}