Ищем единственный дубль в массиве

Зодачга

 

Дан массив произвольного размера с числами в пределах от 1 до 1,000,000. В этом массиве все числа уникальные, кроме одного числа, которое повторяется два раза. Найти это число. Решить эту задачу с минимальным использованием процессорного времени.

 

Листинг кода

 

<?php

$rounds = 500;

include_once 'array1000';
include_once 'array10000'; // dublicate in the end
include_once 'array1000_2';
include_once 'array10000_2'; // dublicate in the begining

echo 'Find with subarray $_temp[] by key';
echo '<ul>';
$total = 0;
foreach ($arrays as $array) {
	$time_pre = microtime(true);
	for($i = 0; $i < $rounds; $i++) {
		$_temp = [];
		foreach($array as $index) {
			if (isset($_temp[$index])) {
				break;
			}
			$_temp[$index] = true;
		}
	}
	$time_post = microtime(true);
	$exec_time = round($time_post - $time_pre,2);
	$total += $exec_time;
	echo '<li>';
	echo '<b>' . $index.'</b> &mdash; '.$exec_time . ' secs';
	echo '</li>';
}
echo '</ul>';
echo 'Total: <b>'. $total .' sec</b>';
echo '<br><br><br>';

/* -------------------------------------------------------------------------- */

echo 'Find with sort()';
echo '<ul>';
$total = 0;
foreach ($arrays as $array) {
	$time_pre = microtime(true);
	for($i = 0; $i < $rounds; $i++) {
		sort($array);
		foreach($array as $index) {
			if ($index === $prev) {
				break;
			}
			$prev = $index;
		}
	}
	$time_post = microtime(true);
	$exec_time = round($time_post - $time_pre,2);
	$total += $exec_time;
	echo '<li>';
	echo '<b>' . $index.'</b> &mdash; '.$exec_time . ' secs';
	echo '</li>';
}
echo '</ul>';
echo 'Total: <b>'. $total .' sec</b>';
echo '<br><br><br>';

/* -------------------------------------------------------------------------- */

echo 'Find with array_search() & array_count_values()';
echo '<ul>';
$total = 0;
foreach ($arrays as $array) {
	$time_pre = microtime(true);
	for($i = 0; $i < $rounds; $i++) {
		$index = array_search(2, array_count_values($array));
	}
	$time_post = microtime(true);
	$exec_time = round($time_post - $time_pre,2);
	$total += $exec_time;
	echo '<li>';
	echo '<b>' . $index.'</b> &mdash; '.$exec_time . ' secs';
	echo '</li>';
}
echo '</ul>';
echo 'Total: <b>'. $total .' sec</b>';
echo '<br><br><br>';

 

 

Результат выполнения

Find with subarray $_temp[] by key

  • 340118 — 0.11 secs
  • 400970 — 1.87 secs
  • 347870 — 0.07 secs
  • 572723 — 0.74 secs

Total: 2.79 sec


Find with sort()

  • 340118 — 0.1 secs
  • 400970 — 1.74 secs
  • 347870 — 0.11 secs
  • 572723 — 1.8 secs

Total: 3.75 sec


Find with array_search() & array_count_values()

  • 340118 — 0.08 secs
  • 400970 — 1.25 secs
  • 347870 — 0.07 secs
  • 572723 — 1.18 secs

Total: 2.58 sec

Мои PET-проекты
Матч Шредингера. Про футбол без спойлеров. Сервис помогает выбрать интересный матч для просмотра в записе. Перейти »
MafiozZz. Сервис для тех, кто любит играть в мафию. Сервис дает клубам возможность завести клубный сайт, предоставляет удобный интерфейс для ведения подобной статистики, расписания игр, выдавать игрокам награды, проводь адресную SMS рассылку (и прочие плюшки). Перейти »