剑指 Offer 39. 数组中出现次数超过一半的数字
题目: 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素
示例.png
分析: 题中提到数组中有一个数字出现的次数超过数组长度的一半, 重点是有 真的存在不可能不存在这样的元素明白吗 ?
思路一: 对数组进行排序, 排序后如果肯定有出现次数超过一半的那么肯定在中间
时间复杂度: O(nlogn)
空间复杂度: O(nlogn)
class Solution {
public int majorityElement(int[] nums) {
//0.边界判断
if(nums==null||nums.length==0) return -1;
//1.题意是数组中有次数超过一半的数字 让找出来
Arrays.sort(nums);
//2.题意是数组中有次数超过一半的数字 让找出来, 脑筋急转弯如果有倒推中间的数字肯定就是这个数字了
return nums[nums.length>>1];
}
}
思路1提交结果.png
思路二 : 用哈希表来计数: key: 元素值 val: 元素出现的次数, 一趟循环即可找到这样元素 (此思路是通用方式: 不管有没有要寻找的元素 只要有就能找到)
时间复杂度: O(n)
空间复杂度: O(n)
class Solution {
public int majorityElement(int[] nums) {
//0.边界判断
if(nums==null||nums.length==0) return -1;
//1.定义需要的数据结构
Map<Integer,Integer> map = new HashMap();
//2.遍历
for(int i = 0;i < nums.length;i++) {
//key:nums[i] val:出现次数
int count = (map.containsKey(nums[i]))?(map.get(nums[i])+1):1;
//更新元素出现的次数
map.put(nums[i],count);
//找到合适的元素
if(map.get(nums[i]) > (nums.length>>1)) return nums[I];
}
return -1;
}
}
思路2提交结果.png
