HashMap,Bit-manipulation and Boyer-Moore solution


  • 1
    C
    public int majorityElement(int[] nums) {
        int threshold = nums.length / 2;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
        	int curCount = (map.containsKey(nums[i]) ? map.get(nums[i]) : 0) + 1;
            map.put(nums[i], curCount);
            if(curCount >= threshold) return nums[i];
        }
        return -1;
    }
    
    public int majorityElement(int[] nums) {
        int threshold = nums.length / 2;
        int ret = 0;
        for (int i = 0; i < 32; i++) {
        	int count = 0;
    		for (int j = 0; j < nums.length; j++)
    			count += (nums[j]>>i) & 1;
    		ret |= count > threshold? (1 << i) : 0;
    	}
        return ret;
    }
    
    public int majorityElement(int[] nums) {
        int threshold = nums.length / 2;
        int ret = 0;
        int curCount = 0;
        for (int i = 0; i < nums.length; i++) {
    		if(curCount == 0){
    			ret = nums[i];
    			curCount++;
    		}
    		else{
    			curCount = ret == nums[i]? curCount+1 : curCount-1;
    			if(curCount > threshold) break;
    		}
    	}
        return ret;
    }

Log in to reply
 

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