Can any one explain this Java Optimal solution? (20170626, not Moore voting)


  • 0

    This is the code I retrieved from the submission bar graph, currently it's the best-performing Java algorithm. I cleaned the code up a little and re-verified its speed, and it's still 1ms and beats 99.91%.
    I am not very experienced with algorithms and I find this code hard to understand, can anyone shed some light? Also, this code looks like tail-recursion, how would one go about rewriting it to an iterative version?

    public class Solution {
        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);
        }
    }
    

    Thanks for any help offered.

    ====update 2017-06-29 16:50:36====
    cleared the code a little bit more.


  • 0

    Update

    Somebody told me how to relate to this algorithm in general.

    The motivation is to reduce the size of the problem by a factor of at least 2 after each iteration(from length n to length p). In the worst case, there would be lgn iterations. In the best case, there can be only 1 iteration: in the case of [1,2,1,3,1,4,1] for example.

    The invariant is: the overall(original) majority element would stay as the majority element in each iteration's actual argument nums[0]..nums[n-1] (length n, which comes from the previous iteration's p).

    The proof is a little verbose, which I thus would omit here. It's not very complicated though.


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.