剑指Offer 39 - 数组中出现次数超过一半的数
2021-05-01 19:27
标签：范围 cti == offer 超过 set 长度 start end 力扣链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/ 题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。 （以下“众数”特指出现次数超过数组长度一半的数） 思路一：摩尔投票法 基本思路是不断缩小众数所在的范围。假设数A为众数，遍历数组进行“投票”，是A则votes++，不是A则votes--，则当votes为0时，众数必然也是剩余数组中的众数。然后重新选择一个数假定为众数，循环该过程。可以一直将该过程进行到数组末尾的那个数为整个数组真正的众数。 代码： 时间复杂度：O(N) 空间复杂度： O(1) 思路二 排序，数组正中间的数一定是众数。 代码：（快速排序） 时间复杂度：O(NlogN) 空间复杂度：O(1) 思路三 一边遍历数组，一边统计每个数出现次数，记录在Map中。 代码： 时间复杂度：O(Nl) 空间复杂度：O(1) 剑指Offer 39 - 数组中出现次数超过一半的数 标签：范围 cti == offer 超过 set 长度 start end 原文地址：https://www.cnblogs.com/xintangchn/p/13205965.html/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let votes = 0;
let candidate;
for(let i = 0; i ){
if(votes === 0){
candidate = nums[i];
}
if(nums[i] === candidate){
votes++;
}else{
votes--;
}
}
return candidate;
};
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
quickSort(nums, 0, nums.length-1);
return nums[parseInt(nums.length/2)];
};
function quickSort(nums, start, end){
if(start >= end) return;
let left = start+1, right = end;
let pivot = nums[start];
while(left right){
while(nums[left] ;
while(nums[right] > pivot) right--;
if(left >= right) break;
swap(nums, left, right);
}
swap(nums, start, right);
quickSort(nums, start, right - 1);
quickSort(nums, right + 1, end);
}
function swap(nums, a, b){
const tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
const map = new Map();
for(let num of nums){
if(map.has(num)){
map.set(num, map.get(num)+1);
}else{
map.set(num, 1);
}
}
for(let key of map.keys()){
if(map.get(key) > nums.length/2)
return key;
}
};