专门做推广的网站吗,免费建域名网站,广州注册公司费用,地方网站开发内容1.数组中出现次数超过一般的数字2.数组中出现一次的数字3.颜色分类问题
1.数组中出现次数超过一半的数字
这是剑指offer中的一道题目#xff0c;数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。
例如#xff1a;输入如下所示的一个长度为9…内容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;MapInteger, 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(arraynull||array.length0)return 0;int len array.length;int resultarray[0];int times1;for(int i1;ilen;i){if(times0){resultarray[i];times1;continue;}if(array[i]result)times;elsetimes--;}times0;for(int i0;ilen;i){if(array[i]result)times;if(timeslen/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) {SetInteger set new HashSetInteger();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;}}}
