Majority Number I & II & III

Majority Number I (找一个出现次数>1/2的数)

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Solution: 用的抵消的思想,如果两个数不一样大,就相互抵消,一样大就保留, 用count计数

public int majorityNumber(ArrayList<Integer> nums) {
    int candidate = -1;
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (count == 0) {
            candidate = nums.get(i);
            count++;
        } else {
            if (candidate == nums.get(i)) {
                count++;
            } else {
                count--;
            }
        }
    }
    return candidate;
}

Majority Number II (找一个出现次数>1/3的数)

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Example

Given [1, 2, 1, 2, 1, 3, 3], return 1.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(1) extra space.

Solution: 策略和I一样,只是现在有两个candidate,

public int majorityNumber(ArrayList<Integer> nums) {
    int candidate1 = -1;
    int candidate2 = -1;
    int count1 = 0;
    int count2 = 0;
    for (Integer num : nums) {
        if (candidate1 == num) {
            count1 ++;
        } else if (candidate2 == num) {
            count2 ++;
        } else if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }
    if (count1 == 0) {
        return candidate2;
    }
    if (count2 == 0) {
        return candidate1;
    }
    count1 = 0;
    count2 = 0;
    for (Integer num : nums) {
        if (num == candidate1) {
            count1++;
        }
        if (num == candidate2) {
            count2++;
        }
    }
    return count1 > count2 ? candidate1 : candidate2;
}

Majority Number III (找一个出现次数>1/k的数)

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Example

Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(k) extra space

Solution: Similar approach as I & II

public int majorityNumber(ArrayList<Integer> nums, int k) {
    Map<Integer, Integer> majorityCounts = new HashMap<>();
    for (Integer num : nums) {
        if (majorityCounts.containsKey(num)) {
            majorityCounts.put(num, majorityCounts.get(num) + 1);
        } else {
            if (majorityCounts.size() < k - 1) {
                majorityCounts.put(num, 1);
            } else {
                List<Integer> toBeRemoved = new ArrayList<>();
                for (Integer key : majorityCounts.keySet()) {
                    if (majorityCounts.get(key) > 1) {
                        majorityCounts.put(key, majorityCounts.get(key) - 1);
                    } else {
                        toBeRemoved.add(key);
                    }
                }
                //important here: can not remove the element while iterating the set
                //which will cause ConcurrentModificationException
                for (Integer key : toBeRemoved) {
                    majorityCounts.remove(key);
                }
            }
        }
    }
    Set<Integer> results = majorityCounts.keySet();
    int maxCount = 0;
    int candidate = 0;
    for (Integer key : majorityCounts.keySet()) {
        majorityCounts.put(key, 0);
    }
    for (Integer num : nums) {
        if (majorityCounts.containsKey(num)) {
            int count = majorityCounts.get(num) + 1;
            majorityCounts.put(num, count);
            if (count > maxCount) {
                maxCount = count;
                candidate = num;
            }
        }
    }
    return candidate;
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *