A binary search solution assuming the input array is sorted, beats 99%


  • 2
    J

    everyone is posting moore's voting solution which is very nice. but if the input array is sorted we can do it in O(lgn) time. sometimes the interviewer may expect this solution rather than moore's voting.

    public class Solution {
        public List<Integer> majorityElement(int[] nums) {
            if(nums.length == 0) return new LinkedList<>();
            List<Integer> ans = new LinkedList<>();
            Arrays.sort(nums);
            int cand1 = nums[nums.length/3];
            int cand2 = nums[2*nums.length/3];
            if(cand1 == cand2){
                ans.add(cand1);
                return ans;
            }
            int len1 = binarySearch(nums, false, cand1) - binarySearch(nums, true, cand1)+1;
            if(len1 > nums.length/3) ans.add(cand1);
            int len2 = binarySearch(nums, false, cand2) - binarySearch(nums, true, cand2)+1;
            if(len2 > nums.length/3) ans.add(cand2);
            return ans;
        }
        
        int binarySearch(int[] nums, boolean op, int target){
            int ans = 0;
            int left = 0, right = nums.length-1;
            while(left <= right){
                int mid = left + (right-left)/2;
                if(nums[mid] == target){
                    ans = mid;
                    if(op){
                        right = mid-1;
                    }else{
                        left = mid+1;
                    }
                }else if(nums[mid] < target){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            return ans;
        }
    }
    

  • 0

    How can you sort an array in O(lgn) time complexity?


  • 0
    I

    @胖得滚起来 Please read the title carefully. The author assumes the input array is sorted.


Log in to reply
 

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