Lettcode_169_Majority Element

본 고 는 학습 중의 총 결 입 니 다.전재 하 는 것 을 환영 하지만 출처 를 밝 혀 주 십시오.http://blog.csdn.net/pistolove/article/details/42247887
Given an array of size n, find the majority element. The majority element is the element that appears more than  ⌊ n/2 ⌋  times.
You may assume that the array is non-empty and the majority element always exist in the array.
생각:
(1)문 제 는 성형 배열 을 정 하고 배열 의 길이 의 절반 이상 의 숫자 를 찾 는 것 이다.
(2)이 문 제 는 간단 하 다.Arrays 클래스 에 익숙 하 다 면,그 중의 sort()방법 으로 배열 을 정렬 하고,정렬 을 마 친 후 왼쪽 에서 오른쪽으로 배열 을 옮 겨 다 니 며,count 기록 이 숫자 를 옮 겨 다 니 는 횟수 를 설정 하고,배열 의 길이 가 절반 이상 이면 되 돌려 줍 니 다.
(3)이 문 제 는 상기 방법 을 사용 하지 않 으 면 한 번 만 옮 겨 다 니 면 결 과 를 얻 을 수 있 습 니 다.여 기 는 더 이상 잔소리 하지 않 습 니 다.아래 코드 를 자세히 보 세 요.
(4)본문 이 당신 에 게 도움 이 되 기 를 바 랍 니 다.
알고리즘 코드 는 다음 과 같 습 니 다.
public static int majorityElement(int[] num) {
	if(num==null ||num.length==0) return-1;
	if(num!=null &&num.length==1) return num[0];
	
	Arrays.sort(num);
	
	int count = 1;
	int flag = 0;
	for (int i = flag+1; i < num.length; i++) {
		if(num[flag]==num[i]){
			count++;
			if(count>num.length/2){
				return num[flag];
			}
		}else{
			flag=i;
			count=1;
		}
	}
	
	return -1;
}

알고리즘 을 한 번 만 옮 겨 다 니 는 코드 는 다음 과 같 습 니 다.
public static int majorityElement(int[] num) {
	if (num == null || num.length == 0)
		return -1;
	int count = 0;
	int index = 0;
	for (int i = 0; i < num.length; ++i) {
		if (index == 0)
			count = num[i];
		if (count == num[i])
			++index;
		else
			--index;
	}
	return count;
}

좋은 웹페이지 즐겨찾기