內(nèi)容	1.數(shù)組中出現(xiàn)次數(shù)超過一般的數(shù)字
	2.數(shù)組中出現(xiàn)一次的數(shù)字
	3.顏色分類問題

1.數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

這是劍指offer中的一道題目，數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。

例如：輸入如下所示的一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)5次，超過了數(shù)組長度的一半，因此輸入2，如果不存在則輸出0。

對于沒有思路的問題，我們的策略都是先在腦子里快速過一遍常見的數(shù)據(jù)結構和常見的算法策略，看看誰能幫我們解決問題，所以很多問題就會自然而然的出現(xiàn)多種解法。

首先，用排序行不行？這里說一定存在出現(xiàn)次數(shù)超過一半的數(shù)字了，那么先對數(shù)組進行排序。在一個有序數(shù)組中次數(shù)超過一半的必定是中位數(shù)，所以可以直接去出中位數(shù)。如果不放心，可以再遍歷數(shù)組，確認一下這個數(shù)字是否出現(xiàn)次數(shù)超過一半。OK，沒問圖，第一種方法就出來了。這種方法的時間復雜度取決于排序算法的時間復雜度，最快的為O(nlogn)。由于排序的代價比較高，所以我們繼續(xù)找其他方法。

其次，用Hash行不行？我們先創(chuàng)建一個HashMap的key是元素的值，value是已經(jīng)出現(xiàn)的次數(shù)，然后遍歷數(shù)組來統(tǒng)計所有元素出現(xiàn)的次數(shù)。最后再遍歷Hash，找到出現(xiàn)次數(shù)超過一半的數(shù)字。OK第二種方法出來了。

代碼：

方法一：

 public static int moreThanHalfNum(int[] array) {if (array == null)return 0;Map<Integer, Integer> res = new HashMap<>();int len = array.length;for (int i = 0; i < array.length; i++) {res.put(array[i], res.getOrDefault(array[i], 0) + 1);if (res.get(array[i]) > len / 2)return array[i];}return 0;}

第二種方法

 /*** 方法二：比較特殊的計數(shù)法* @param array* @return*/public static int moreThanHalfNum2(int [] array) {if(array==null||array.length==0)return 0;int len = array.length;int result=array[0];int times=1;for(int i=1;i<len;i++){if(times==0){result=array[i];times=1;continue;}if(array[i]==result)times++;elsetimes--;}times=0;for(int i=0;i<len;i++){if(array[i]==result)times++;if(times>len/2)return result;}return 0;}public static int majorityElement(int[] nums) {int count = 0;Integer candidate = null;for (int num : nums) {if (count == 0) {candidate = num;}count += (num == candidate) ? 1 : -1;}return candidate;}

2.數(shù)組中只出現(xiàn)一次的數(shù)字

LeetCode136.鏈接

/*** 基于集合尋找* @param arr* @return*/public static Integer findOneNum(int[] arr) {Set<Integer> set = new HashSet<Integer>();for (int i : arr) {if (!set.add(i))//添加不成功返回false，前加上！運算符變?yōu)閠rueset.remove(i);//移除集合中與這個要添加的數(shù)重復的元素}//注意邊界條件的處理if (set.size() == 0)return null;//如果Set集合長度為0，返回null表示沒找到return set.toArray(new Integer[set.size()])[0];}

/*** 基于位運算* @param arr* @return*/public static int findOneNum2(int[] arr) {int flag = 0;for(int i : arr) {flag ^= i;}return flag;}

3.顏色分類問題（荷蘭國旗問題）

LeetCode75鏈接???????

public static void sortColors(int[] nums) {int n = nums.length;int left = 0;//將所有的0交換到數(shù)組的最前面for (int right = 0; right < n; right++) {if (nums[right] == 0) {int temp = nums[right];nums[right] = nums[left];nums[left] = temp;left++;}}//將所有的1交換到2的前面for (int right = left; right < n; ++right) {if (nums[right] == 1) {int temp = nums[right];nums[right] = nums[left];nums[left] = temp;++left;}}}

?