最近2018中文字幕在日韩欧美国产成人片_国产日韩精品一区二区在线_在线观看成年美女黄网色视频_国产精品一区三区五区_国产精彩刺激乱对白_看黄色黄大色黄片免费_人人超碰自拍cao_国产高清av在线_亚洲精品电影av_日韩美女尤物视频网站

題目鏈接

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

題目描述

找出數(shù)組中重復(fù)的數(shù)字。

在一個(gè)長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0 ～ n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，
但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個(gè)
重復(fù)的數(shù)字。

示例 1：

輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3

限制：

2 <= n <= 100000

解題方案

思路 1

• 標(biāo)簽：哈希
• 使用 HashSet 來進(jìn)行處理，因?yàn)?HashSet 本身不允許出現(xiàn)重復(fù)元素，所以     當(dāng)添加元素失敗或已經(jīng)包含該數(shù)字時(shí)，則表示出現(xiàn)了重復(fù)元素，將其返回即可。思路較為簡單，就不給圖了
• 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)

代碼 1

• Java 版本

class Solution {
   public int findRepeatNumber(int[] nums) {
       Set numsSet = new HashSet<>();
       for(int num: nums) {
           if(!numsSet.add(num)) {
               return num;
           }
       }
       return -1;
   }
}

• JavaScript 版本

/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
   const numsSet = new Set();
   for(const num of nums) {
       if(numsSet.has(num)) {
           return num;
       } else {
           numsSet.add(num);
       }
   }
   return -1;
};

思路 2

• 標(biāo)簽：哈希
• 從題目描述中我們可以看出，因?yàn)樗袛?shù)字都在 0 ～ n-1 的范圍內(nèi)，其實(shí)完全可以省掉額外的空間開辟，將每個(gè)位置的數(shù)交換映射到其對應(yīng)的數(shù)組下標(biāo)下面，當(dāng)出現(xiàn)新的元素與其對應(yīng)的下標(biāo)中的數(shù)字相等時(shí)，即為重復(fù)數(shù)字
• 這本質(zhì)還是哈希的思想，思路 1 是使用庫函數(shù)申請額外空間，思路 2 則是數(shù)組本身做哈希表，達(dá)到了節(jié)省空間的目的
• 此處會(huì)用到 while 循環(huán)，原因是保證交換過來的新元素位置也要正確
• 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)

代碼 2

• Java 版本

class Solution {
   public int findRepeatNumber(int[] nums) {
       int len = nums.length;
       for (int i = 0; i < len; i++) {
           while (nums[i] != i) {
               if (nums[i] == nums[nums[i]]) {
                   return nums[i];
               }
               int temp = nums[i];
               nums[i] = nums[temp];
               nums[temp] = temp;
           }
       }
       return -1;
   }
}

• JavaScript 版本

/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
   const len = nums.length;
   for (let i = 0; i < len; i++) {
       while (nums[i] != i) {
           if (nums[i] == nums[nums[i]]) {
               return nums[i];
           }
           const temp = nums[i];
           nums[i] = nums[temp];
           nums[temp] = temp;
       }
   }
   return -1;
};

畫解 2

橫滑見完整畫解