清华大学学生工作做网站互联网营销师培训学校

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

问题描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。详见剑指offer39

问题分析

最直接的方式就是使用hashMap,遍历给定数组，将数字和对应出现次数存储在hashMap中，然后再遍历hashMap，找到出现次数最大的数字。除此之外，我们还可以将数据进行排序，升序和降序均可，排序后，出现次数超过一半的元素一定出现在数组的中位数位置。除此之外，还有一种巧妙解法，设立两个变量，num和count，num用于存储当前遍历到的元素，count用于存储次数,如果count为0，则当前元素不可能是出现次数超过一半的元素，则遍历下一个元素。

代码实现

使用HashMap解法

public int majorityElement(int[] nums) {Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){if(map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i])+1);}else{map.put(nums[i],1);}}int maxCount = Integer.MIN_VALUE;int maxNum = Integer.MIN_VALUE;for(int num:map.keySet()){if(map.get(num)>maxCount){maxCount = map.get(num);maxNum = num;}}return maxNum;
}

使用排序解法

public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length/2];
}

巧妙解法

public int majorityElement(int[] nums) {int result=0;int count=0;for(int num:nums){if(count==0){result = num;}count += result==num?1:-1;}return result;
}

数组中只出现一次的数字

问题描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。详见leetcode136

问题分析

使用HashMap存储数组元素和元素出现的次数，遍历HashMap，找到出现一次的元素,或者利用HashSet存储元素，利用集合的不可重复性，如果可以添加到集合中，说明当前遍历到的元素在数组中出现一次，直接添加，如果不能添加，说明当前遍历到的元素在数组中出现两次，移除HashSet中的当前元素，最后返回HashSet中的元素，即为数组中只出现一次的元素。除此之外，我们还可以利用位运算来实现。遍历数组元素，进行异或运算，出现两次的元素异或运算结果为0，所有元素的异或运算结果为数组中只出现一次的元素

代码实现

使用HashSet

public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for(int num: nums){if(!set.add(num)){set.remove(num);}}Integer[] array = set.toArray(new Integer[set.size()]);return array[0];
}

使用异或运算

public int singleNumber(int[] nums) {int res = 0;for(int num:nums){res^=num;}return res;
}

137. 只出现一次的数字 II

问题描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

问题分析

使用HashMap存储数组元素和元素出现的次数，遍历HashMap，找到出现一次的元素。另外我们也可以使用位运算来实现对于出现3次的元素，每一位为0或者1,相加为0或者3，可以将每一位相加后对3取余，即为只出现一次的元素的对应位的值。

代码实现

使用位运算实现

public int singleNumber(int[] nums) {int res = 0;for(int i=0;i<32;i++){int total = 0;for(int num:nums){total+=((num>>i)&1);}if(total%3!=0){res |= (1<<i);}}return res;
}

总结

元素出现次数问题通用方法就是使用HashMap存储元素和对应次数，或许遍历map即可得到想要出现次数的元素。这种方法需要遍历一次数组，遍历一次map，使用一个map，时间复杂度为O(n),空间复杂度为O(n)，面试时，可能不允许使用Hash或者集合，即需要我们设计O(n)时间复杂度,常数空间复杂度的算法。此时我们可以考虑常数计数或者为运算等常见方式。