1. 問題描述
找出數組中重復的數字。
在一個長度為 n 的數組 nums 里的所有數字都在 0~n-1 的范圍內。數組中某些數字是重復的,但不知道有幾個數字重復了,也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。
示例 1:
輸入:[2, 3, 1, 0, 2, 5, 3]
輸出:2 或 3
2. 解題詳情
由于只需要找出數組中任意一個重復的數字,因此遍歷數組,遇到重復的數字即返回。為了判斷一個數字是否重復遇到,使用集合存儲已經遇到的數字,如果遇到的一個數字已經在集合中,則當前的數字是重復數字。
偽代碼如下:
1.初始化集合為空集合,重復的數字 repeat = -1;
2.遍歷數組中的每個元素:
3.將該元素加入集合中,判斷是否添加成功;
4.如果添加失敗,說明該元素已經在集合中,因此該元素是重復元素,將該元素的值賦給 repeat,并結束遍歷。
時間復雜度:O(n)O(n)。
遍歷數組一遍。使用哈希集合(HashSet),添加元素的時間復雜度為 O(1)O(1),故總的時間復雜度是 O(n)O(n)。
空間復雜度:O(n)O(n)。不重復的每個元素都可能存入集合,因此占用 O(n)O(n) 額外空間。
class Solution {public int findRepeatNumber(int[] nums) {Set<Integer> set = new HashSet<Integer>();int repeat = -1;for (int num : nums) {if (!set.add(num)) {repeat = num;break;}}return repeat;}
}