第3题 – 数组中重复的数字

作者: 周伟林 分类: 剑指offer 发布时间: 2018-05-13 13:34

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

解题思路

找到数组中第一个重复的数字。

JavaScript实现

方法一: 利用hash数组。plain

function duplicate(numbers, duplication)
{
    // write code here
    //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    //函数返回True/False
    let len = numbers.length, hash = {};
    for(let i = 0; i < len; ++i){
        if(numbers[i] in hash){
            duplication[0] = numbers[i];
            return true;
        }else{
            hash[numbers[i]] = 1;
        }
    }
    return false;
}

方法二: 利用数据为[0,n-1]的特点,进行交换。

function duplicate(numbers, duplication)
{
    for(let i = 0; i < numbers.lenght; ++i){
        if(numbers[i] < 0 || numbers[i] > n-1)
            return false;
    }
    
    for(let i = 0; i < numbers.length; ++i){
        while(numbers[i] !== i){
            if(numbers[i] === numbers[numbers[i]]){ // 注意:判断要放在循环里面
                duplication[0] = numbers[i];
                return true;
            }
            let tmp = numbers[i];
            numbers[i] = numbers[tmp];
            numbers[tmp] = tmp;
        }
    }
    return false;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注