Array: check on duplicates
14.03.2014
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 )