Определите, появляется ли число только один раз в массиве

Это своего рода вопрос о домашнем задании, я долго об этом думал, и придумал пару решений, но я думаю, что существует лучший вариант.

Какой самый быстрый способ определить, есть ли в массиве элемент (int), который появляется только один раз? Любой элемент может появляться любое количество раз. {3, 1, 4, 1, 4, 3} вернет false, а {3, 1, 4, 1, 4, 1} вернет true (3 появляется один раз).

Нам разрешено использовать только те вещи, которые мы уже изучили (все основы, рекурсия, oop, поиск и сортировка algos, включая quicksort), поэтому создание хеш-таблицы не является вариантом.

Пока лучшее практическое решение, которое я придумал, сортирует его с помощью quicksort, затем проходит через него (O (nlogn)), лучшее непрактичное решение, которое я придумал, делает большой массив размером всех возможных значений int и а затем использовать его, похожую на хэш-таблицу (но этот массив слишком большой, чтобы фактически реализовать) (O (n))

Есть ли другой (практический) способ сделать это в O (n) времени?

EDIT: только что получил ответ от TA, предлагаемое решение O (n), о котором я слышал, было непрактичным (то же или похожее на то, что я предложил), и поэтому они сказали нам не использовать его. Я на 99% уверен, что лучший практический ответ (без хэш-таблиц) - это время O (nlogn).

Ответ 1

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

Когда вы выбрали значение поворота и перемещаетесь через соответствующую часть массива, ЕСЛИ это значение совпадает с точкой поворота, отбросьте его и отбросьте значение поворота после того, как вы переместили часть массива, это приведет к удалению дубликатов ПЕРЕД матрицей в конечном итоге сортируется.

Sorting [5, 1, 4, 1, 4, 1]
If you choose the pivot as 4, you'd end up with the 2 sub arrays being:
[1, 1, 1] and [5]

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

Таким образом вы можете забрать разные значения МНОГО раньше.

Изменить: Да, это все еще ограничено O (nlogn) (я думаю?)

Ответ 2

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

Но как только вы найдете тот, который появляется один раз, вы можете сломаться. Этот код сделает это. Это O (n ^ 2), но я не уверен, что вы можете сделать это быстрее.

boolean anySingles(int[] data])
{
 outer:
 for (int i = 0; i < data.length - 1; i++)
 {
  for (int j = 0; i < data.length; j++)
  {
   if (i != j)
   {
    if (data[i] == data[j]) continue outer;
   }
  }
  // made it to the end without finding a duplicate
  return true;
 }
 return false;
}

Ответ 3

Проведите эксперимент:

package test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * User: Nicholas
 * Date: 15.05.13
 * Time: 21:16
 */
public class Searcher {

    private static boolean searchBySorting(int [] array){
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray,0, array.length);

        Arrays.sort(newArray);
        for (int i = 0; i < newArray.length - 2; ++i){
            if(newArray[i] == newArray[i + 1]){
                return true;
            }
        }

        return false;
    }

    private static boolean searchByCompare(int [] array){
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray,0, array.length);

        for (int i = 0; i < newArray.length - 1; ++i){
            int value = newArray[i];
            for(int j = i + 1; j < newArray.length - 1; ++j){
                if(value == newArray[j]){
                    return true;
                }
            }
        }

        return false;
    }

    private static boolean searchBySet(int [] array){
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray,0, array.length);

        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < newArray.length; ++i){
            if(set.contains(newArray[i])){
                return true;
            }

            set.add(newArray[i]);
        }

        return false;
    }

    private static int [] generateRandomArray(){
        Random random = new Random();
        int size = random.nextInt(1000) + 100;
        int [] array = new int[size];

        for (int i = 0; i < size; ++i){
            array[i] = random.nextInt();
        }

        return array;
    }

    public static void main(String [] args){

        long sortingTime = 0;
        long compareTime = 0;
        long setTime = 0;

        for (int i = 0; i < 1000; ++i){
            int [] array = generateRandomArray();

            long begin = System.currentTimeMillis();
            for(int j = 0; j < 100; ++j){
                searchBySorting(array);
            }
            long end = System.currentTimeMillis();
            sortingTime += (end - begin);

            begin = System.currentTimeMillis();
            for(int j = 0; j < 100; ++j){
                searchByCompare(array);
            }
            end = System.currentTimeMillis();
            compareTime += (end - begin);

            begin = System.currentTimeMillis();
            for(int j = 0; j < 100; ++j){
                searchBySet(array);
            }
            end = System.currentTimeMillis();
            setTime += (end - begin);
        }

        System.out.println("Search by sorting: " + sortingTime + " ms");
        System.out.println("Search by compare: " + compareTime + " ms");
        System.out.println("Search by insert: " + setTime + " ms");
    }
}

Мои результаты:

Поиск по сортировке: 2136 мс

Поиск по схожим параметрам: 11955 мс

Поиск по вставке: 4151 мс

Есть ли вопросы?

PS. Лучший алгоритм, который я знаю, Черепаха и заяц