Leecode刷题之旅-C语言/python-169求众数

时间:2024-07-25 21:34:08
/*
* @lc app=leetcode.cn id=169 lang=c
*
* [169] 求众数
*
* https://leetcode-cn.com/problems/majority-element/description/
*
* algorithms
* Easy (58.05%)
* Total Accepted: 27.2K
* Total Submissions: 46.7K
* Testcase Example: '[3,2,3]'
*
* 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
*
* 你可以假设数组是非空的,并且给定的数组总是存在众数。
*
* 示例 1:
*
* 输入: [3,2,3]
* 输出: 3
*
* 示例 2:
*
* 输入: [2,2,1,1,1,2,2]
* 输出: 2
*
*
*/
int majorityElement(int* nums, int numsSize) {
int count=,result=nums[];
int i;
for(i=;i<numsSize;i++){
nums[i]==result?count++:count--;
if(!count){
result=nums[i];
count++;
}
}
return result;
}

这里用的是投票法,如果下一个数还和这个数相等的话,count+1,否则count-1

当count等于0的时候结果被赋值为当前的数,count加一。

---------------------------------------------------------------------------

python:

#
# @lc app=leetcode.cn id=169 lang=python3
#
# [169] 求众数
#
# https://leetcode-cn.com/problems/majority-element/description/
#
# algorithms
# Easy (58.05%)
# Total Accepted: 27.2K
# Total Submissions: 46.7K
# Testcase Example: '[3,2,3]'
#
# 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
#
# 你可以假设数组是非空的,并且给定的数组总是存在众数。
#
# 示例 1:
#
# 输入: [3,2,3]
# 输出: 3
#
# 示例 2:
#
# 输入: [2,2,1,1,1,2,2]
# 输出: 2
#
#
#
class Solution(object):
def majorityElement(self, nums):
res=set(nums)
n=len(nums)/2
for item in res:
if(nums.count(item)>n):
return item

这里应该是用了歪门邪道了。。。判断概率是否大于二分之一。