【問題描述】[數(shù)組中的重復(fù)數(shù)字][簡(jiǎn)單]

找出數(shù)組中重復(fù)的數(shù)字。 在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。輸入： [2, 3, 1, 0, 2, 5, 3] 輸出：2 或 3

【解答思路】

1. 排序后比較

時(shí)間復(fù)雜度：O(NlogN) 空間復(fù)雜度：O(1)

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

2. HashSet

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

public int findDuplicate(int[] nums) {HashSet<Integer> set = new HashSet<>();for (int i = 0; i <= nums.length - 1; i++) {if (set.contains(nums[i])) {return nums[i];}else{set.add(nums[i]);}}return -1; }

3.原地置換

時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public int findRepeatNumber(int[] nums) {int i = 0;while(i < nums.length) {if(nums[i] == i) {i++;continue;}if(nums[nums[i]] == nums[i]) return nums[i];int tmp = nums[i];nums[i] = nums[tmp];nums[tmp] = tmp; //nums[nums[i]], nums[i] = nums[i], nums[nums[i]]，為什么這里的交換可以讓元素的 索引 與 值 相等。//下面供大家方便看出來（因?yàn)槲铱戳撕镁貌欧磻?yīng)過來）：//記num[ i ] =a，num[num[ i ] ]=num[ a ]=b,那么 交換后，num[ i ]=b, num[num[i]]=num[a]=a，這時(shí)候下標(biāo) a 對(duì)應(yīng)的元素也是a，達(dá)到目的}return -1;} }

【總結(jié)】

1.考察的是程序員的溝通能力，先問面試官要時(shí)間/空間需求

• 時(shí)間優(yōu)先就用字典，
• 有空間要求，就用指針+原地排序數(shù)組
• 要求空間O(1)并且不能修改原數(shù)組，還得寫成二分法

2.靈活思路 一題多解

3. HashMap 或 HashSet常見用法

3.1 HashSet

新建 HashSet<Integer> set = new HashSet<>();

（1）增加
public boolean add(E e);
（2）刪除
public boolean remove(Object j);
（3）對(duì)比查找
public boolean contains(Object j);
（4）清空集合
public void clear();
（5）獲取長(zhǎng)度
public int size();
3.2 HashMap

新建 HashMap<String,Integer> map= new HashMap<String,Integer>();

（1） 插入鍵值對(duì)數(shù)據(jù)
public V put(K key, V value)
（2）根據(jù)鍵值獲取鍵值對(duì)值數(shù)據(jù)
public V get(Object key)
（3）獲取Map中鍵值對(duì)的個(gè)數(shù)
public int size()
（4）判斷Map集合中是否包含鍵為key的鍵值對(duì)
public boolean containsKey(Object key)
（5）判斷Map集合中是否包含值為value的鍵值對(duì)
boolean containsValue(Object value)
（6）判斷Map集合中是否沒有任何鍵值對(duì)
public boolean isEmpty()
（7）清空Map集合中所有的鍵值對(duì)
public void clear()
（8）根據(jù)鍵值刪除Map中鍵值對(duì)
public V remove(Object key)

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[03]题[数组中的重复数字][HashSet]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。