JS找出数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

  • 示例 1:

输入:[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:2 <= n <= 100000

  • 解题思路:

1.常规思路就是把输入的数组排序,然后从排序的数组中找到重复的数字只需要从头到尾扫描排序后的数组即可。排序一个长度为n的数组需要O(nlogn)的时间复杂度

2.第二种思路就是利用哈希表来解决。从头到尾扫描数组中的数字,每扫描一个数字,就用O(1)的时间去判断哈希表里是否包含该数字,如果哈希表里已经存在该数字,就找到一个重复的数字,如果哈希表里面没有这个数字,就把它加入哈希表。这个思路的时间复杂度为O(n),空间复杂度为O(n)

3.我们现在把数组的索引利用起来;从头到尾扫描这个数组中的数字,当扫描到下标为i的数字时,首先比较这个数字(用m表示)是不是等于i,如果是则接着扫描下一个数字;如果不是,则拿它和第m个数字进行比较,如果它和第m个数字相等,就找到了一个重复的数字(该数字在下标为i和m的位置都出现了);如果它和第m个数字不相等,就把第i个数字和第m个数字交换,把m放到属于它的位置。接下来再重复这个比较、交换的过程,直到我们发现一个重复的数字

方法一:利用数组排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    var m=[];
    if (nums == null || nums.length < 0) {
        return -1;
    }
    // 题目的条件是数组 nums 里的所有数字都在 0~n-1 的范围内
    for (let i = 0, length = nums.length; i < length; i++) {
        if (nums[i] < 0 || nums[i] > length - 1) {
        return -1;
        }
    }
   // 排序
    nums=nums.sort();
    for(var i=0;i<nums.length-1;i++){    
        if(nums[i]==nums[i+1]) {
            return nums[i];
        }           
    }
} 
findRepeatNumber([2,3,1,0,2,5,3]);

方法二:利用哈希表

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    if (nums == null || nums.length < 0) {
      return -1;
    }
    // 题目的条件是数组 nums 里的所有数字都在 0~n-1 的范围内
    for (let i = 0, length = nums.length; i < length; i++) {
      if (nums[i] < 0 || nums[i] > length - 1) {
        return -1;
      }
    }
    // 哈希表
    let map = new Map();
    for(let i of nums){
        if(map.has(i)) return i;
        map.set(i, 1);
    }
    return null;
};
findRepeatNumber([2,3,1,0,2,5,3]);

方法三:原地交换

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
  if (nums == null || nums.length < 0) {
    return -1;
  }
  // 题目的条件是数组 nums 里的所有数字都在 0~n-1 的范围内
  for (let i = 0, length = nums.length; i < length; i++) {
    if (nums[i] < 0 || nums[i] > length - 1) {
      return -1;
    }
  }
  // 思路就是把数字放到对应的索引上  比方说数字3放到索引3的位置
  for (let i = 0; i < nums.length; i++) {
    // 如果当前数字跟对应的索引不相同则交换
    while (nums[i] != i) {
      if (nums[i] == nums[nums[i]]) {
        return nums[i];
      }
      let temp = nums[i];
      nums[i] = nums[temp];
      nums[temp] = temp;
    }
  }
  return -1;
};
findRepeatNumber([2,3,1,0,2,5,3]);
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目一:找出数组中重复的数字 题目描述 在一个长度为n的数组里面所有的数字都在0~n-1的范围内。数组中某些数字是...
    一个学霸阅读 463评论 0 0
  • 找出数组中重复的数字 在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几...
    Longshihua阅读 606评论 0 3
  • 最近在刷题,准备记录一些值得参考的题目,也希望通过这种方式可以让自己印象更加深刻,本篇文章将讨论 数组中重复的数字...
    AaricChen阅读 263评论 0 1
  • 题目描述 在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了...
    灵活的胖墩阅读 256评论 0 3
  • 找出数组中任意一个重复的数字! 思路1:把数组排序,从排序后的数组中找出重复的数字。但排序一个长度为n的数组需要O...
    带带吴腾跃阅读 261评论 0 0