MajorityElementOPT [source code]

public class MajorityElementOPT {
    public int majorityElement(int[] nums) {
        return maj(nums, nums.length);
    }

    public int maj(int[] nums, int n) {
        if (n == 1 || n == 2) return nums[0];
        int p = 0;
        for (int i = 0 ; i < n; i = i + 2) {
            if (i == n - 1 || nums[i] == nums[i + 1]) {
                nums[p++] = nums[i];
            }        
        }
        return maj(nums,p);
    }

    public static void main(String[] args) {
        MajorityElementOPT tester = new MajorityElementOPT();
        int[] input1 = {1,2,1,3,1,4,1};
        System.out.println(tester.majorityElement(input1));
    }
}

这个是 submission 最优解, 1ms, 99.9%.

这个算法在地里发帖求助了之后才知道到底怎么理解(guoye 也没有办法讲清楚), 这个 recursion 理解的核心在于要理解 invariant: the overall majority element will always be the majority element of each nums[0]..nums[p - 1].
具体的证明在地里.

这个人设计这个算法的思路是在THE majority element的身份不被改变的情况下, 不断缩小整个问题的 size, 也就是 length(by a factor of at least 2 each iteration). 这个算法的 worstcase 并不优秀, 但是比较针对 lc 给出的testcase;

另外, 这一题其实还有不少其他的思路:

Randomization

随便挑一个, 检查是不是majority

class Solution {  
public:  
    int majorityElement(vector<int>& nums) {  
        int n = nums.size();  
        srand(unsigned(time(NULL)));  
        while (true) {  
            int idx = rand() % n;  
            int candidate = nums[idx];  
            int counts = 0;   
            for (int i = 0; i < n; i++)  
                if (nums[i] == candidate)  
                    counts++;   
            if (counts > n / 2) return candidate;  
        }  
    }  
};

Divide and Conquer

class Solution {  
public:  
    int majorityElement(vector<int>& nums) {  
        return majority(nums, 0, nums.size() - 1);  
    }  
private:  
    int majority(vector<int>& nums, int left, int right) {  
        if (left == right) return nums[left];  
        int mid = left + ((right - left) >> 1);  
        int lm = majority(nums, left, mid);  
        int rm = majority(nums, mid + 1, right);  
        if (lm == rm) return lm;  
        return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;  
    }  
};

Problem Description

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:46.19%
Contributor: LeetCode
Companies
adobe zenefits
Related Topics
array divide and conquer bit manipulation
Similar Questions
Majority Element II