題目

給定一個長度為 n 的整數數組 nums，數組中所有的數字都在 0∼n−1 的範圍內。

數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。

請找出數組中任意一個重複的數字。

注意：如果某些數字不在 0∼n−1 的範圍內，或數組中不包含重複數字，則返回 -1。

樣例

給定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

解題思路

從題目我們可以知道，數組長度為 n，所有數字都在 0~n-1 範圍內。如果元素不重複，那麼數組應該就是 [0, 1, 2, ...n-1]（假設給數組排完了序）。也就是說，遞增排序後，數組中的元素值與其對應的下標應該是相同的，即下標為 0 的元素值也是 0，以此類推。

首先，我們可以遍歷數組，若存在元素不在 0~n-1 的範圍內，直接返回 -1。

接著，再次遍歷數組，若下標 i 與對應元素 nums[i] 不同，即 nums[i] != i，我們應該把 nums[i] 這個元素交換到正確的位置 nums[i]上。交換前，先判斷 nums[i] 與 nums[nums[i]] 這兩個元素是否相同，相同說明存在重複元素，直接返回，否則進行 swap 交換。交換過後，我們需要再次判斷 i 位置上的元素，因此，我們使用 while 循環。

可對照下方代碼實現，加深理解。

100% AC 代碼

class Solution {
 public int duplicateInArray(int[] nums) {
 int n = nums.length;
 
 // 若存在數組元素不在[0, n-1] 的範圍內，直接返回-1
 for (int num : nums) {
 if (num < 0 || num >= n) {
 return -1;
 }
 }
 
 for (int i = 0; i < n; ++i) {
 while (nums[i] != i) {
 if (nums[i] == nums[nums[i]]) {
 // 說明位置i與位置nums[i]上的元素相同，直接返回該重複元素
 return nums[i];
 }
 swap(nums, i, nums[i]);
 }
 }
 return -1;
 
 }
 
 private void swap(int[] nums, int i, int j) {
 int t = nums[i]; 

 nums[i] = nums[j];
 nums[j] = t;
 }
}

 _.._ ,------------.
 ,' `. ( We want you! )
 / __) __` \\ `-,----------'
 ( (`-`(-') ) _.-'
 /) \\ = / (
 /' |--' . \\
 ( ,---| `-.)__`
 )( `-.,--' _`-.
 '/,' ( Uu",
 (_ , `/,-' )
 `.__, : `-'/ /`--'
 | `--' |
 ` `-._ /
 \\ (
 /\\ . \\. offer
 / |` \\ ,-\\
 / \\| .) / \\
 ( ,'|\\ ,' :
 | \\,`.`--"/ }
 `,' \\ |,' /
 / "-._ `-/ |
 "-. "-.,'| ;
 / _/["---'""]
 : / |"- '
 ' | /
 ` |

作者：yanglbme
原文鏈接：https://juejin.im/post/5dd29e1f5188254a1f446545

閱讀更多 追逐仰望星空 的文章

關鍵字: 二面 Java虛擬機 算法