class Solution {
public:
int majorityElement(vector<int>& nums) {
}
};
面试题 17.10. 主要元素
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
输入：[1,2,5,9,5,9,5,5,5] 输出：5
示例 2：
输入：[3,2] 输出：-1
示例 3：
输入：[2,2,1,1,1,2,2] 输出：2
原站题解
javascript 解法, 执行用时: 60 ms, 内存消耗: 43 MB, 提交时间: 2023-09-15 14:50:41
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let candidate = -1;
let count = 0;
for (const num of nums) {
if (count === 0) {
candidate = num;
}
if (num === candidate) {
count++;
} else {
count--;
}
}
count = 0;
const length = nums.length;
for (const num of nums) {
if (num === candidate) {
count++;
}
}
return count * 2 > length ? candidate : -1;
};
cpp 解法, 执行用时: 16 ms, 内存消耗: 18.6 MB, 提交时间: 2023-09-15 14:50:27
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int& num : nums) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
count = 0;
int length = nums.size();
for (int& num : nums) {
if (num == candidate) {
count++;
}
}
return count * 2 > length ? candidate : -1;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 47.6 MB, 提交时间: 2023-09-15 14:50:14
class Solution {
public int majorityElement(int[] nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
count = 0;
int length = nums.length;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
return count * 2 > length ? candidate : -1;
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-09-15 14:49:48
impl Solution {
pub fn majority_element(nums: Vec<i32>) -> i32 {
let (mut count, mut ret, len) = (1, nums[0], nums.len());
for i in 1..len {
count = if nums[i] == ret { count+1 } else { count-1 };
if count == 0 { ret = nums[i]; count = 1; }
}
if nums.into_iter().filter(|&x| x == ret).map(|x| 1).sum::<usize>() * 2 > len { ret } else { -1 }
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 17.9 MB, 提交时间: 2023-09-15 14:46:09
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate, count = -1, 0
for num in nums:
if count == 0:
candidate = num
if num == candidate:
count += 1
else:
count -= 1
cnt = 0
for num in nums:
if num == candidate:
cnt += 1
if cnt > len(nums) // 2:
return candidate
return -1
golang 解法, 执行用时: 16 ms, 内存消耗: 6 MB, 提交时间: 2021-07-09 11:33:36
func majorityElement(nums []int) int {
candidate, count := -1, 0
for _, num := range nums {
if count == 0 {
candidate = num
}
if num == candidate {
count++
} else {
count--
}
}
cnt := 0
for _, num := range nums {
if num == candidate {
cnt++
}
}
if cnt > len(nums)/2 {
return candidate
}
return -1
}
php 解法, 执行用时: 56 ms, 内存消耗: 20.8 MB, 提交时间: 2021-05-14 18:59:19
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function majorityElement($nums) {
$count = 0;
$candidate = null;
// 遍历过程中, 众数的出现$count+1, 非众数出现$count-1, 最终$count>0
foreach ( $nums as $num ) {
if ( $count == 0 )
$candidate = $num;
$count += $num == $candidate ? 1 : -1;
}
if ( $count > 0 ) {
$n = 0;
foreach ( $nums as $num ) {
if ( $num == $candidate )
$n++;
}
if ( $n > count($nums) / 2)
return $candidate;
}
return -1;
}
}