小白学Java之数组问题——第三关黄金挑战

内容	1.数组中出现次数超过一般的数字
	2.数组中出现一次的数字
	3.颜色分类问题

1.数组中出现次数超过一半的数字

这是剑指offer中的一道题目，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如：输入如下所示的一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现5次，超过了数组长度的一半，因此输入2，如果不存在则输出0。

对于没有思路的问题，我们的策略都是先在脑子里快速过一遍常见的数据结构和常见的算法策略，看看谁能帮我们解决问题，所以很多问题就会自然而然的出现多种解法。

首先，用排序行不行？这里说一定存在出现次数超过一半的数字了，那么先对数组进行排序。在一个有序数组中次数超过一半的必定是中位数，所以可以直接去出中位数。如果不放心，可以再遍历数组，确认一下这个数字是否出现次数超过一半。OK，没问图，第一种方法就出来了。这种方法的时间复杂度取决于排序算法的时间复杂度，最快的为O(nlogn)。由于排序的代价比较高，所以我们继续找其他方法。

其次，用Hash行不行？我们先创建一个HashMap的key是元素的值，value是已经出现的次数，然后遍历数组来统计所有元素出现的次数。最后再遍历Hash，找到出现次数超过一半的数字。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;}

第二种方法

 /*** 方法二：比较特殊的计数法* @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.数组中只出现一次的数字

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，前加上！运算符变为trueset.remove(i);//移除集合中与这个要添加的数重复的元素}//注意边界条件的处理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交换到数组的最前面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;}}}