Услуги Сертификаты Новости Статьи База знаний Алгоритмы Портфолио Скачать Ссылки Поиск
Услуги arrow База знаний arrow Algorithms arrow Array: check on duplicates
Array: check on duplicates Версия для печати Отправить на e-mail
Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like. Do not sort the array or use bit vectors. Try to work within the array without using any other temporary data structures. Do not use 2 nesting for loops since the time complexity would be high. Try to find a solution by executing just one loop. Hint: manipulate the elements of the same array as you loop through.

var hasDuplicates = function(arr) {
    var index;
    for (var i = 0, len = arr.length; i < len; i++) {
        index = Math.abs(arr[i]) - 1;
        if (arr[index] > 0) {
            arr[index] = (-1) * arr[index];
        } else {
            return true;
    return false;
Последнее обновление ( 14.03.2014 )