数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2以C++为例
时间: 2024-05-27 22:14:58 浏览: 9
int majorityElement(int* nums, int numsSize){
int count = 0;
int candidate;
for(int i=0; i<numsSize; i++){
if(count == 0){
candidate = nums[i];
}
if(nums[i] == candidate){
count++;
}else{
count--;
}
}
return candidate;
}
//主函数
int main(){
int nums[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
int numsSize = sizeof(nums) / sizeof(int);
int result = majorityElement(nums, numsSize);
printf("%d", result);
return 0;
}
相关问题
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
解法1:哈希表
遍历数组,用哈希表记录每个数字出现的次数,如果某个数字出现的次数超过数组长度的一半,就返回该数字。
时间复杂度:O(n)
空间复杂度:O(n)
解法2:排序
将数组排序,由于该数字出现的次数超过数组长度的一半,所以该数字一定是数组的中间元素。
时间复杂度:O(nlogn)
空间复杂度:O(1)
解法3:摩尔投票法
遍历数组,用一个计数器记录当前数字出现的次数,如果遇到相同的数字,计数器加1,否则计数器减1。如果计数器变为0,就将下一个数字作为候选数字。最后留下的候选数字就是出现次数超过数组长度一半的数字。
时间复杂度:O(n)
空间复杂度:O(1)
Python代码:
c++分治法求数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
解法一:排序法
先将数组排序,由于该数字出现的次数超过数组长度的一半,所以排序后中间的数一定是该数字。
时间复杂度:O(nlogn)
解法二:哈希表法
遍历数组,将每个数字出现的次数存入哈希表中,最后遍历哈希表找到出现次数超过数组长度一半的数字。
时间复杂度:O(n),但需要额外的空间来存储哈希表。
解法三:摩尔投票法
由于该数字出现的次数超过数组长度的一半,所以可以使用一个计数器和一个候选数字,遍历数组,如果当前数字与候选数字相同,则计数器加1,否则计数器减1,如果计数器为0,则更新候选数字为当前数字。最后剩下的候选数字即为结果。
时间复杂度:O(n)
以下是摩尔投票法的Python代码实现:
def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)