?記錄一下算法題的學習10

只出現一次的數字

leetcode題目：給你一個?非空?整數數組?nums?，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。你必須設計并實現線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間

技巧? 位運算 異或運算 Java中異或運算符^? 異或運算性質三種

• 任何數和0做異或運算，結果仍然是原來的數，即 a⊕0=a。
• 任何數和其自身做異或運算，結果是 0，即 a⊕a=0。
• 異或運算滿足交換律和結合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

代碼展示

class Solution {public int singleNumber(int[] nums) {int sole=0;//遍歷整個數組里的元素，由于題目所給條件除了某個元素只出現一次以外，其余每個元素均出現兩次//合理使用異或運算的特點//我們最終獲得的就是只出現一次的元素for(int num=0;num<nums.length;num++){ sole^=nums[num];}return sole;}
}

?多數元素

leetcode題目：給定一個大小為?n?的數組?nums?，返回其中的多數元素。多數元素是指在數組中出現次數?大于?? n/2 ??的元素。你可以假設數組是非空的，并且給定的數組總是存在多數元素。

1.摩爾投票法??核心理念為?票數正負抵消

• 候選人(candidates)初始化為 nums[0]，票數 count 初始化為 1。
• 當遇到與candidates 相同的數，則票數 count = count + 1，否則票數 count = count - 1。
• 當票數 count 為 0 時，更換候選人，并將票數 count 重置為 1。
• 遍歷完數組后，candidates 即為最終答案

class Solution {public int majorityElement(int[] nums) {int candidates= nums[0], count = 1;for (int i = 1; i < nums.length; ++i) {if (candidates == nums[i])count+=1;else if ( --count == 0) {candidates = nums[i];count = 1;}}return candidates;}
}

2.數組排序法? 將數組 nums 排序，數組中點的元素 一定為眾數。代碼展示

class Solution {public int majorityElement(int[] nums) {//數組升序Arrays.sort(nums);int most_number=0; //初始化多數元素--》眾數為0most_number=nums[nums.length/2]; //將數組 nums 排序，數組中點的元素 一定為眾數。return most_number;}
}

class Solution {public int majorityElement(int[] nums) {//數組降序 jdk8使用Integer[] integers = Arrays.stream(nums).boxed().toArray(Integer[]::new);Arrays.sort(integers ,Collections.reverseOrder ());int most_number=0; //初始化多數元素--》眾數為0most_number=integers[integers.length/2]; //將數組 nums 排序，數組中點的元素 一定為眾數。return most_number;}
}

?注意

• ?如果想要使用降序：Arrays.sort(scores,Collections.reverseOrder());。
• 首先要注意的是不能用int這個類型了，要用Integer，不能使用基本類型（int,double, char）
• 如果是int型需要改成Integer，float要改成Float

舉例Integer[] 和int[] 互轉 jdk8使用Stream流來實現互相轉化

// int[] --> Integer[]
int[] arr = {1, 2, 3, 4, 5};
Integer[] integers = Arrays.stream(nums).boxed().toArray(Integer[]::new);
// Integer[] --> int[]
int[] nums = Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();

3.哈希表統計法：?遍歷數組?nums?，用 HashMap 統計各數字的數量，即可找出眾數

hashmap.getOrDefault(Object key, V defaultValue)

class Solution {public int majorityElement(int[] nums) {HashMap<Integer,Integer> map=new HashMap<>();//建立一個哈希表for(int i=0;i<nums.length;i++){map.put(nums[i],map.getOrDefault(nums[i],0)+1);//將nums集合里面的元素添加到哈希表中}int key = 0;int value = 0;//哈希表遍歷，找到眾數for(Map.Entry<Integer,Integer> entry:map.entrySet()){if(entry.getValue()>value){value = entry.getValue();key = entry.getKey();}}return key;}
}

?結束拜拜！