Basic Java Answer for Majority Element II


  • 0
    K

    My basic java version, passed in 420ms, welcome advice. Using two variables to store temporarily possible answers, verify in the end.

    public static List<Integer> majorityElement(int[] nums) {
    	List<Integer> res = new ArrayList<Integer>();
    	int first_val = 0, second_val = 0;
    	int first_count = 0, second_count = 0;
    	for (int i = 0; i < nums.length; i++) {
    		if (first_count == 0) {
    			first_val = nums[i];
    			first_count = 1;
    		} else if (nums[i] == first_val) {
    			first_count++;
    		} else if (second_count == 0) {
    			second_val = nums[i];
    			second_count = 1;
    		} else if (nums[i] == second_val) {
    			second_count++;
    		} else {
    			first_count--;
    			second_count--;
    		}
    	}
    	checkMajorityHelper(res, nums, first_count, first_val, second_count,
    			second_val);
    	return res;
    }
    
    private static void checkMajorityHelper(List<Integer> res, int[] nums,
    		int first_count, int first_val, int second_count, int second_val) {
    	int count1 = 0, count2 = 0, len = nums.length;
    	for (int i = 0; i < len; i++) {
    		if (first_count > 0 && nums[i] == first_val) {
    			count1++;
    		} else if (second_count > 0 && nums[i] == second_val) {
    			count2++;
    		}
    	}
    	if (count1 > len / 3) {
    		res.add(first_val);
    	}
    	if (count2 > len / 3) {
    		res.add(second_val);
    	}
    }

  • 0
    Q

    You're doing 3 iterations over the array. Last 2 could be combined.


  • 0
    R

    Good solution


  • 0
    J

    Hi, I think you should check whether first == second. If they're the same, you may get identical elements in the result list.


  • 0
    K

    Same value is checked first before assigning it to an empty spot, so after iteration, first_val and second_val will not hold same value.


  • 0
    K

    @qgambit2 updated, thanks!


Log in to reply
 

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