leetcode-majority-element

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/majority-element/

　　找到数组中出现次数超过n/2的那个数

题目分析

　　最开始的思路是基于hashmap，时间和空间复杂度都是O(N)，看了讨论区的答案可以基于一种计数+抵消的方式，空间复杂度O(1)就能解。ans变量为最终结果，cnt为计数变量，遇到一个数如果等于ans直接cnt++，如果不等那么将cnt—（相当于抵消了一次）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int majorityElement(int[] nums) {
        int ans = nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) { // 注意cnt==0直接赋值
                ans = nums[i];
                cnt = 1;
            } else if (nums[i] == ans) {
                cnt++;
            } else {
                cnt--;
            }
        }
        return ans;
    }
}