Leetcode/169Majority_Element.java at main · yayajjiang/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        int count = 1;
        int max = 0;
        int element = 0;
        if(length == 1){
            return nums[0];
        }
        for(int i = 0; i < length-1; i++){
            if(nums[i] == nums[i+1]){
                count++;
                //System.out.println(count );
                if(i == length - 2){
                    if(count > max && count > length/2){
                        max = count;
                        element = nums[i];
                    }
                }
            }else{
                //System.out.println(count + " " + max + " " + length/2);
                if(count > max && count > length/2){
                    max = count;
                    element = nums[i];
                }
                count = 1;
            }
        }
        return element;
    }
}

//moore
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

author：LeetCode-Solution
link：https://leetcode.cn/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/