Найти два равных элемента в одном массиве

Question

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

Answer 1

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

Ну, нам не нужно быть таким глупым. Разумеется, мы можем добавить порядок, отсортировав массив: O (nlog (n)). А после этого просто пройдите через массив и найдите два с одинаковым значением O (n).

Лучше тогда это трудно сделать, что делает нижнюю границу O (nlog (n)).

Answer 2

Пожалуйста, сформулируйте вашу проблему: какой алгоритм вы используете?

Вообще:

Нижняя граница: В худшем случае, если вы, конечно, должны прочитать на каждом индексе массива, то есть п операции.

Обесценивая проблему: Если у вас ограниченный домен, вы можете использовать другой массив A, который будет проиндексирован элементами домена. В A [i] вы сохраните #occurences i в своем массиве. Если вам нужно найти позиции элементов, вы можете иметь массив связанных списков.

Почему O (n log n): Если у вас есть массив элементов, где единственная операция, которую вы можете использовать, - это прямое сравнение, вы не можете использовать этот трюк. Но вы можете использовать некоторый словарь, такой как структура данных, с доступом O (log n), и вы приходите с O (n log n). Я бы хотел увидеть элегантное доказательство этого.

Почему не O (n): Представьте, что у вас есть массив, в котором нет равных элементов. Можете ли вы показать это в O (n)? Это невозможно сделать быстрее, чем сортировка массива, если вы думаете об этом. И сортировка в общем случае в лучшем случае O (n log n).

Answer 3

Через HashMap вы можете найти общий элемент в одном массиве с сложностью O (n). Следуйте этому Java-коду.

public class Main { 

    public static void main(String[] args) { 
     System.out.println("Hello World!"); 
     Main repeat = new Main(); 
     int arr[] = {4, 12, 4, 5, 12, 3, 1,0,6,22,7,15,15}; 
     int arr_size = arr.length; 
     repeat.printRepeating(arr, arr_size);; 

    } 
    void printRepeating(int arr[], int size) 
    { 
     HashMap<Integer,Integer> map = new HashMap<Integer, Integer>(); 
     ArrayList <Integer> comon=new ArrayList<>(); 
     int i; 

     System.out.println("Repeated elements are : "); 
     for (i = 0; i < size; i++) 
     { 
      if (map.containsKey(arr[i])) 
      System.out.println(arr[i]+""); 
      else 
       map.put(arr[i],arr[i]); 
     } 
    } 
}