Как быстро найти повторяющийся элемент в массиве ???

Привет всем! Ребята подскажите правильно ли я мыслю или можно куда быстрее решить задачу? Есть массив от 1 до 1000000. В этом массиве все числа уникальные, кроме одного числа, которое повторяется два раза. Найти это число.
Решить эту задачу с минимальным использованием процессорного времени.


Мой вариант:

Код (Text):

1. <?php
2.    
3.    
4.     for ($i = 1; $i <= 100000; $i++)
5.         {
6.             $array[$i] = $i;
7.         }
8.             $array[$i+1] = 8;
9.        
10.            
11.    
12.     define("START_TIMER", microtime(true));
13.    
14.     $numberlist_new = array_count_values ($array);
15.    
16.     foreach($numberlist_new as $k => $v)
17.     {
18.         if ($v > 1) {
19.         echo "Мы нашли повторяющееся число: <b>$k</b></br>\n";    
20.         }
21.        
22.     }
23.    
24.     printf("Время работы скрипта: %.5f с", microtime(true)-START_TIMER);
25.  
26. ?>

Время работы скрипта: 0.03120 сек.

Добавлено спустя 3 минуты 13 секунд:
Кстати памяти не хватает на массив 10 (6). Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 36 bytes)

 

Ну то, что я придумал - я написал выше. А увеличивать запас ОЗУ не хотелось бы, т.к в будущем можно обезопасить себя от возникновения подобной проблемы.

 

Я уже второй день читаю, кто-то предлагает для работы с большими массивами метод битовых карт, кто-то метод сравнения. Много похожих задач в нете. С некоторыми решениями я крайне не согласен, некторые алгоритмы, которые мне удалось найти - работаю медленнее моего. Хотя при 10 * в 6 степени мой тоже уступать стал одному из вариантов.

 

Я в своем примере тоже использую array_count_values. Но при n=1000000 , вот эта функция быстрее рабтает :

Код (Text):

1. function search_deplicate($array) {
2.     $hash = array();
3.     foreach ($array as $val) {
4.         if (isset($hash[$val])) {
5.             return $val;
6.         }
7.         $hash[$val] = true;
8.     }
9.     return null;
10. }

Добавлено спустя 5 минут 31 секунду:
Ваш вариант, крут 0.30160 с

Добавлено спустя 10 минут 18 секунд:
Спасибо за помощь!!!

 

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