An array of arbitrary size is given with numbers ranging from 1 to 1,000,000. In this array, all numbers are unique, except for one number, which is repeated two times. Find this number. Solve the problem with minimal use of CPU time.

This is such an interesting task. All ideas are accepted.

This solution came to mind:

$result=array(); $true=true; for($i=0;!$result[$v=$array[$i]]&&$i<ARRAY_ELEMENT_COUNT;$i++){ $result[$v]=&$true; unset($v); } $number=$array[$i];

What other ideas you can apply?

The numbers in the array are mixed:

  define('ARRAY_ELEMENT_COUNT',1000); $array=array(); for($index=0;$index<ARRAY_ELEMENT_COUNT;$index++) $array[$index]=$index+1; shuffle($array); //Добавим повторяющийся елемент srand((float)microtime() * 1000000);// эта команда для чистоты эксперимента $pos=&rand(0,ARRAY_ELEMENT_COUNT-1); do{ $val=rand(1,ARRAY_ELEMENT_COUNT-1); }while($array[$pos]==$val); $array[$pos]=$val; unset($val,$pos);
  • one
    I did not understand the conditions: $ result [$ v = $ array [$ i]] Do all numbers go in succession or how? If the numbers are mixed randomly, then this is not a valid code. It's not clear yet - why check $ i <ARRAY_ELEMENT_COUNT; //? It is written in the task - in the array 100% there will be a repeating number, accordingly such a check (I’m not about the real code, but strictly from the TZ of the task) is meaningless. At each iteration you check this condition (which is absolutely unnecessary in the context of this task). Well, $ i ++ is slower ++ $ i: D - Zowie
  • I agree, but I think the problem with the trick and the lack of checks for errors will be considered incompetence. And the condition! $ Result [$ v = $ array [$ i]] is about the same as isset ($ result [$ v = $ array [$ i]]). For ++ $ i special thanks! Well, the numbers are mixed. Now I'll throw off how I fill it for tests. - org
  • so WHY DOES THIS CHECK NEED? .. Just the same, IMHO, the task is purely academic , therefore you will not be considered to be competent in no way. Several clarifications - what is the maximum array length and is it possible, for example, that $ arr [0] - number, $ arr [1] - does not exist, $ arr [2] - again number, $ arr [3] - does not exist ...? PS: I still do not understand - please explain how array_diff can help (even theoretically)? I'm just not asylil - Zowie
  • array_diff ($ source array, $ same array but without duplicate elements = array_unique ($ source array)) I think so? - org
  • one
    @org - with array_diff everything is really logical, I just didn’t really wake up: D But with tz both memory and performance - the solution, to put it mildly, is not the best ... - Zowie

5 answers 5

Well, this should help:

 $arr1 = array(1,2,3,6,1,0,4,5,8,15,149); // здесь две единицы. $arr2 = array_unique($arr1); $arr3 = array_diff_assoc($arr1,$arr2); print_r($arr3); // выводит "[4]->1"

Only need to use "array_diff_assoc()"

    @org , you have the correct algorithm, but the code is just awful. Why do you sculpt & wherever? And what a terrible cycle like that? My version:

     function search_deplicate($array) { $hash = array(); foreach ($array as $val) { if (isset($hash[$val])) { return $val; } $hash[$val] = true; } return null; }

    The tests gave the following results :

      org: 0.011948854923248 sec Asen: 0.04189505815506 sec drdaeman: 0.0067547178268433 sec Ilya: 0.0036947202682495 sec
    • Yes, a good method, the best, perhaps, if the memory is not running out. It's a pity there are no normal sets in PHP, it would be even more beautiful with them. Gentlemen, plus this answer! - drdaeman

    If you feel sorry for the memory for a partial second copy (in the worst case, the second copy without one element), sort ( O(n log n) , most likely) and run linearly through the array ( O(n) , I hope), looking for two identical ones in a row, an item.

    This is a cheaper option with array_unique / array_diff_* in both time and memory. Tests guarantee it (but do not trust, but check it yourself).

    If memory is not a pity - see the answer @ Ilya Pirogov , he is the fastest. Run through the array, save everything we see in the hashmap (poor man's set), if you have already seen the element, it means we found it.

    • one
      Something I got wrong 2 times on one test ... it’s really much faster than any option with diff. @drdaeman - forgive me for forcing you to write so many tests, I, in fact, are not out of malice, simply, apparently you shouldn’t conduct any tests on Sunday: D - Zowie
    • one
      All right, nothing to apologize for. That you excuse me, that pounced and forced to sit-recheck. I am also not from evil, but solely for the sake of truth :) - drdaeman
    • And if we can not touch the original array? That memory is multiplied by two times. By the way, my tests showed that my method overtakes array_diff_assoc - org
    • @org - and if we can't touch the source array, then this is another task; D - Zowie

    You can probably somehow through array_unique () and array_diff solve the issue.

    • I'll never know how they help solve the problem? .. - Zowie
    • Yes, I also tried this option, but in time it loses to mine. And you can use it like this: array_diff ($ array, array_unique ($ array)); - will give an array of all duplicate elements. - org
    • Are we not feeding him arrays in the amount of two pieces? - org
    • Indeed, I apologize, the time is earlier: D - Zowie
    • This is perhaps the best way to solve the problem. Plus) - AseN
     $array = array(...); $keys = array_flip(array_flip($array)); for ($i = 0; $i < count($array); $i++) if (!isset($keys[$i])) { echo $array[$i]; break; }

    I wonder how long it will be.

    • It will be long, long: D $ i <count ($ array) - Zowie