LeetCode - 169.229. Majority Element II (JAVA) 주요 원소

169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appearsmore 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.
한 배열 에서 반수 이상 의 원 소 를 찾아내다.(배열 에는 이러한 요소 가 존재 합 니 다)
정렬:
중간 요소 되 돌리 기
Hashtable (jdk 8 문법)

// Sorting
public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

Moore voting algorithm   
매번 한 쌍 의 서로 다른 요 소 를 찾 아 배열 에서 삭제 하고 배열 이 비어 있 거나 한 가지 요소 만 있 을 때 까지 삭제 합 니 다.원소 e 의 출현 빈도 가 절반 을 넘 으 면 배열 의 마지막 남 은 것 은 e 밖 에 없다 는 것 을 증명 하기 어렵 지 않다.
물론 마지막 에 남 은 원소 도 절반 이상 나타 나 지 않 았 을 수도 있다.예 를 들 어 배열 은 [1, 2, 3] 이 고 마지막 에 남 은 3 은 한 번 밖 에 나타 나 지 않 았 으 며 절반 도 안 되 었 다.이러한 false positive 상황 을 제외 하 는 방법 도 간단 하 다. 원본 배열 을 저장 하고 마지막 으로 스 캔 하여 검증 하면 된다.

	public int majorityElement(int[] nums) {
	    Map map = new HashMap();
	    int ret=0;
	    for (int num: nums) {
	    	map.put(num, map.getOrDefault(num, 0)+1);
	        if (map.get(num)>nums.length/2) {
	            ret = num;
	            break;
	        }
	    }
	    return ret;
	}
}

229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
이전 문제 의 를 거울 로 삼다        Moore voting algorithm   
 하나의 정형 배열 을 지정 하고 모든 주 요 소 를 찾 습 니 다. 배열 에서 나타 나 는 횟수 는 배열 요소 개수 의 3 분 의 1 보다 엄 격 히 많 습 니 다.
3, 3 을 상쇄 하면 마지막 에 두 개의 candidates 가 남 습 니 다. 그러나 이때 누가 다 수 를 차지 하 는 것 이 아니 라 누가 최종 결과 인지 주의 하 세 요. 반 례 [1, 2, 3, 2, 3, 3, 3, 1, 4, 4] 3, 3 을 상쇄 한 후에 남 은 [1, 4, 4] 4 의 수량 이 우세 하지만 결 과 는 1 이 어야 합 니 다. 그래서 3, 3 을 상쇄 한 후에 1 과 4 의 수량 이 len (nums) / 3 을 초과 하 는 지 다시 한 번 반복 해서 찾 습 니 다.

public int majorityElement(int[] nums) {
        int count = 0, ret = 0;
        for (int num : nums) {
            if (count == 0)
                ret = num;
            if (num != ret)
                count--;
            else
                count++;
        }
        return ret;
    }