数组中出现次数超过一半的数字
问题描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。详见剑指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)时间复杂度,常数空间复杂度的算法。此时我们可以考虑常数计数或者为运算等常见方式。
