Массив Домашнее задание Вопрос

Вам дан массив с целыми числами от 1 до 1 000 000. Одно целое число в массиве дважды. Как вы можете определить, какой? Можете ли вы придумать способ сделать это, используя немного дополнительной памяти.

Algo:

Solution 1: Have a hash table Iterate through array and store its elements in hash table As soon as you find an element which is already in hash table, it is the dup element Pros: It runs in O(n) time and with only 1 pass Cons: It uses O(n) extra memory Solution2: Sort the array using merge sort (O(nlogn) time) Parse again and if you see a element twice you got the dup. Pros: it doesn't use extra memory Cons: Running time is greater than O(n)

Can you guys think of any better solution?

Ответы на вопрос(9)

Ваш ответ на вопрос