投票法

发表于 | 分类于 |
字数统计: 816 | 阅读时长 ≈ 4

[TOC]

一半

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

1/3

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
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        /**
        首先可以明确的一点是，这样的元素可能有0个、1个、或者2个，再没有别的情况了. 
        然后，求众数I 里的 Boyer-Moore 算法思路在这里依然可用，但需要些改动：
        1) 满足条件的元素最多有两个，那么需要两组变量. count, major变成了
           count1, major1; count2, major2;
        2) 选出的两个元素，需要验证它们的出现次数是否真的满足条件.
        **/
        List<Integer> ret = new ArrayList<>();
        if(nums.length < 1) return ret;
        int count1 = 0, count2 = 0;
        int major1 = nums[0], major2 = nums[0];
        for(int num : nums) {
            if(num == major1)
                count1++;
            else if(num == major2)
                count2++;
            else if(count1 == 0) {
                count1 = 1;
                major1 = num;
            }
            else if(count2 == 0) {
                count2 = 1;
                major2 = num;
            }
            else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for(int num : nums) {
            if(num == major1)
                count1++;
            else if(num == major2)
                count2++;
        }
        if(count1 > nums.length/3)
            ret.add(major1);
        if(major1 != major2 && count2 > nums.length/3)
            ret.add(major2);
        return ret;
    }
}

n/k

左神的代码写的很好，时间复杂度是O(N*K)，额外空间复杂度O(K)，用map集合保存K个不同的值。一、如果map的大小不超过K，遍历到相同的，value加1，不同的，添加进去。用map.containskey判断是否在容器中，比用数组方便。
二、如果map大小达到K，遍历到相同的，所有键的值减1，如果值变成0，要删除。这时候引出一全体键值都减1的函数，左神用了遍历map，如果要删除的键放进一个链表里。
三、判断map中剩下的值出现次数是否大于N/K

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
53
54
55
56
57
58
59
60
61
62
63
64
65
public class hello {//100 999
    public static void printKMajor(int[] arr, int K) {
        if (K < 2) {
            System.out.println("the value of K is invalid.");
            return;
        }
        HashMap<Integer, Integer> cands = new HashMap<Integer, Integer>();
        for (int i = 0; i != arr.length; i++) {
            if (cands.containsKey(arr[i])) {
                cands.put(arr[i], cands.get(arr[i]) + 1);
            } else {
                if (cands.size() == K - 1) {
                    allCandsMinusOne(cands);
                } else {
                    cands.put(arr[i], 1);
                }
            }
        }

        HashMap<Integer, Integer> reals = getReals(arr, cands);
        boolean hasPrint = false;
        for (Map.Entry<Integer, Integer> set : cands.entrySet()) {
            Integer key = set.getKey();
            if (reals.get(key) > arr.length / K) {
                hasPrint = true;
                System.out.print(key + " ");
            }
        }
        System.out.println(hasPrint ? "" : "no such number.");
    }

    public static void allCandsMinusOne(HashMap<Integer, Integer> map) {
        List<Integer> removeList = new LinkedList<Integer>();
        for (Map.Entry<Integer, Integer> set : map.entrySet()) {
            Integer key = set.getKey();
            Integer value = set.getValue();
            if (value == 1) {
                removeList.add(key);
            }
            map.put(key, value - 1);
        }
        for (Integer removeKey : removeList) {
            map.remove(removeKey);
        }
    }

    public static HashMap<Integer, Integer> getReals(int[] arr,
                                                     HashMap<Integer, Integer> cands) {
        HashMap<Integer, Integer> reals = new HashMap<Integer, Integer>();
        for (int i = 0; i != arr.length; i++) {
            int curNum = arr[i];
            if (cands.containsKey(curNum)) {
                reals.put(curNum,reals.getOrDefault(curNum,0)+1);
            }
        }
        return reals;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 1, 1, 2, 1 };
        int K = 4;
        printKMajor(arr, K);
    }
    
}