描述:Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times. You may assume that the array is non-empty and the majority element always exist in the array.

 

思路1:Moore voting algorithm--每找出两个不同的element,就成对删除即count--,最终剩下的一定就是所求的。时间复杂度:O(n)

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int> &num) {
 4 
 5         int elem = 0;
 6         int count = 0;
 7         
 8         for(int i = 0; i < num.size(); i++)  {
 9             
10             if(count == 0)  {
11                 elem = num[i];
12                 count = 1;
13             }
14             else    {
15                 if(elem == num[i])
16                     count++;
17                 else
18                     count--;
19             }
20             
21         }
22         return elem;
23     }
  };

思路2:随机挑选一个元素,检查是否是多数元素。时间复杂度:Average:O(n)。期望查找次数 <2

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int> &num) {
 4 
 5         int count = 0;
 6         
 7         for(;;) {
 8             if(num.size() == 1)
 9                 return num[0];
10             else    {
11                 int i = rand() % (num.size() - 1);
12                 for(int j = 0; j < num.size(); j++) {
13                     if(num[j] == num[i])
14                         count++;
15                 }
16                 if(count > (num.size() / 2))
17                     return num[i];
18                 else    {
19                     count = 0;
20                     continue;
21                 }
22             }
23         }
24     }
  };

附LeetCode建议解决方案:

标签智能推荐:

【python学习笔记】文本文件操作之os模块

ects\OJ\simple\practice.py')print(fileSplit)fileSplit=os.path.split(r'\Users\zz\PycharmProjects\OJ\simple')print(fileSplit)('\\Users\\zz\\PycharmProjects\\OJ\\simple','practice.py')('\\Users\\zz\\Pych

面试记录---pico (字节) wifi (2022春节前)

结果:一面不通过主要内容:wlan相关知识,oj编程题失败原因:&nbsp;oj编程题没写完

收藏这些网站让你学费省下好几万

ing可视化编辑器免费的H5一:刷题类网站牛客网-----IT题库,java,前端面试题LeetCode-----刷题网站HOOJ----杭电OJ适合新手小白去刷题POJ------北大OJ很多编程大佬Lintcode-----刷题网站算法学习二:&nbsp;自学编程的网站(免费视频)菜鸟StackOverflow-----遇到问题90%都可解决腾讯公开课中国大学mooc-----最好的在线课程学

Index

Tableofcontents目录TableofcontentsOJ-Improvemyself,better.Leetcode洛谷OJ-Improvemyself,better.Leetcode洛谷

JavaScript 13.3

1.数组对象练习练习一:&nbsp;练习二:

HDOJ 2057 A+B again

0){cout&lt;&lt;"-"&lt;&lt;hex&lt;&lt;uppercase&lt;&lt;-result&lt;&lt;endl;}elsecout&lt;&lt;hex&lt;&lt;uppercase&lt;&lt;result&lt;&lt;endl;}return0;-心得体会本题的解决需要了解十六进制数的输入输出格式,如果没有这些知识的积累,就难以完成这一题目,不仅过程

Fontainebleau Demo 2019.3.x网盘链接

github地址:https://github.com/Unity-Technologies/FontainebleauDemo压缩包7.4GB:链接:https://pan.baidu.com/s/1XlUZBJMOsQV2ry9gyNFYrQ提取码:18oj

关于本blog主

博客文章,未经作者准许,禁止转载。坐标HN-CS。各大OJ账号:洛谷:bits。,UID:112943CF:zqyyyAtcoder:zqyyyloj:zhangqiyu

文件操作

&nbsp;&nbsp;真题练习&nbsp;

java初学

1.集合应用练习2.总结