Лучший способ написать эту программу

Question

У меня есть общий вопрос по программированию, который я использовал для ответа на Java. Это вопрос:

Учитывая массив целых чисел, напишите программу, чтобы узнать, сколько чисел, которые не являются уникальными, находятся в массиве. (например, в {2,3,2,5,6,1,3} 2 числа (2 и 3) не являются уникальными). Сколько операций выполняет ваша программа (в нотации O)?

Это мое решение.

int counter = 0;


for(int i=0;i<theArray.length-1;i++){
for(int j=i+1;j<theArray.length;j++){
    if(theArray[i]==theArray[j]){
        counter++;
                    break; //go to next i since we know it isn't unique we dont need to keep comparing it.
            }
}
}

return counter:

Теперь, в моем коде каждый элемент сравнивается с любым другим элементом, поэтому существует около n (n-1) / 2 операций. Давать О (п ^ 2). Пожалуйста, скажите мне, если вы считаете, что мой код неверен / неэффективен или мое O-выражение неверно.

Answer 1

Ваш анализ верен, но вы можете легко получить его до O (n) времени.Попробуйте использовать HashMap<Integer,Integer> для хранения ранее увиденных значений во время итерации по массиву (ключ - это число, которое вы видели, значение - это количество раз, которое вы видели).Каждый раз, когда вы пытаетесь добавить целое число в hashmap, проверяйте, есть ли оно там.Если это так, просто увеличьте счетчик целых чисел.Затем, в конце, пройдитесь по карте и посчитайте, сколько раз вы видите ключ с соответствующим значением больше 1.

Answer 2

Почему бы не использовать Map, как в следующем примере:

// NOTE! I assume that elements of theArray are Integers, not primitives like ints
// You'll nee to cast things to Integers if they are ints to put them in a Map as
// Maps can't take primitives as keys or values
Map<Integer, Integer> elementCount = new HashMap<Integer, Integer>();
for (int i = 0; i < theArray.length; i++) {
   if (elementCount.containsKey(theArray[i]) {
     elementCount.put(theArray[i], new Integer(elementCount.get(theArray[i]) + 1));
   } else {
     elementCount.put(theArray[i], new Integer(1));
   }
}

List<Integer> moreThanOne = new ArrayList<Integer>();
for (Integer key : elementCount.keySet()) { // method may be getKeySet(), can't remember
   if (elementCount.get(key) > 1) {
      moreThanOne.add(key);
   }
}

// do whatever you want with the moreThanOne list

Обратите внимание, что этот метод требует повторения по списку дважды (я уверен, что есть способ сделать это повторение один раз).Он повторяется один раз через theArray, а затем снова неявно, поскольку он повторяет набор ключей elementCount, который, если нет двух одинаковых элементов, будет точно таким же большим.Тем не менее, повторение одного и того же списка дважды последовательно все равно равно O (n) вместо O (n ^ 2), и, следовательно, имеет намного лучшую асимптотику.

Answer 3

Ваш код не делает то, что вы хотите. Если вы запустите его, используя массив {2, 2, 2, 2}, вы обнаружите, что он возвращает 2 вместо 1. Вам нужно будет найти способ убедиться, что подсчет никогда не повторяется.

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

Answer 4

Как уже говорили другие, решение O (n) вполне возможно с использованием хеша.В Perl:

my @data = (2,3,2,5,6,1,3);
my %count;
$count{$_}++ for @data;
my $n = grep $_ > 1, values %count;
print "$n numbers are not unique\n";

ВЫХОД

2 numbers are not unique

Answer 5

Во-первых, ваш подход - это то, что я бы назвал "грубой силой", и это действительно O (n ^ 2) в худшем случае. Это также неправильно реализовано, так как числа, которые повторяются n раз, считаются n-1 раз.

Если оставить в стороне, существует несколько способов решения проблемы. Первое (что предложили несколько ответов) - это итерация массива и использование карты для отслеживания того, сколько раз данный элемент был просмотрен. Предполагая, что карта использует хеш-таблицу для основного хранилища, сложность в среднем случае должна быть O (n), так как значения для получения и вставки с карты должны быть в среднем O (1), и вам нужно только выполнить итерации по списку и карте один раз каждый. Обратите внимание, что в худшем случае это все равно O (n ^ 2), поскольку нет гарантии, что хеширование даст результаты с постоянным временем.

Другой подход заключается в том, чтобы сначала просто отсортировать массив, а затем выполнить итерацию отсортированного массива в поисках дубликатов. Этот подход полностью зависит от выбранного метода сортировки и может быть в любом месте от O (n ^ 2) (для наивной сортировки пузырьков) до O (n log n), наихудшего случая (для сортировки слиянием) до O (n log n). ) средний, хотя и вероятный случай (для быстрой сортировки.)

Это лучшее, что вы можете сделать с подходом сортировки, предполагающим произвольные объекты в массиве. Так как в вашем примере используются целые числа, вы можете добиться гораздо большего успеха, используя радикальную сортировку, которая будет иметь сложность O (dn) в худшем случае, где d по существу постоянна (поскольку для 32-разрядных целых чисел она достигает максимума 9).

Наконец, если вы знаете, что элементы являются целыми числами и что их величина не слишком велика, вы можете улучшить решение на основе карты, используя массив размера ElementMax, который гарантировал бы O (n) наихудший случай сложность, с компромиссом, требующим 4 * дополнительных байта памяти ElementMax.

Answer 6

Я думаю, что ваша временная сложность O(n^2) верна.

Если сложность пространства не является проблемой, то вы можете иметь массив из 256 символов (ASCII) стандарта и начать заполнять его значениями. Например // Может быть, вам нужно инициализировать все значения до 0. Я не знаю. Но следующее можно сделать с помощью O(n+m), где n - длина массива, а m - длина массива.

int [] array = new int [256];

для (int i = 0; i

  array[theArray[i]] = array[theArray[i]] + 1;

для (int i = 0; i

  if(array[i] > 1)

        System.out.print(i);