Majority Element

今天是一到有关数学计算的题目，较为简单，来自LeetCode，难度为Easy，Acceptance为37.5%。

题目如下

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.

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

该题的思路较为简单，因为有一个数的出现次数超过了1/2，那么可以得出，其余所有的数字加起来也不到1/2。

利用这个性质，我们可以遍历整个数组，然后让不同的数字相互抵消就可得到最后的结果，具体过程如下：

在遍历的过程中，用一个变量major记录出现次数最多的数字，用另一个变量count记录该数字的出现次数；当遍历每一个数字时，首先比较与major是否相同，若相同则count加一，若不同则count减一，当count减到0时，则将出现最多的数字设为major；则在遍历的最后剩下的数字即为次数最多的数字。

下面我们来看具体代码

代码如下

java版

public class Solution {
    public int majorityElement(int[] num) {

        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;

        }
        return major;
    }
}

c++版

int majorityElement(vector<int> &num) {
    int majorityIndex = 0;
    for (int count = 1, i = 1; i < num.size(); i++) {
        num[majorityIndex] == num[i] ? count++ : count--;
        if (count == 0) {
            majorityIndex = i;
            count = 1;
        }
    }

    return num[majorityIndex];
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image