[검 지 Offer 학습] [면접 문제 29: 배열 에서 절반 이 넘 는 숫자 가 나 왔 습 니 다.]

제목:
배열 에 나타 난 숫자 가 배열 길이 의 절반 을 넘 습 니 다. 이 숫자 를 찾 아 보 세 요. 예 를 들 어 설명 합 니 다.
길이 9 의 배열 ｛ 1, 2, 3, 2, 2, 2, 5, 4, 2｝ 을 입력 하 십시오.숫자 2 가 배열 에서 5 번 나 와 배열 길이 의 절반 을 넘 었 기 때문에 출력 2.
생각:
해법 1: Partition 함수 기반 O (n) 알고리즘
배열 에 나타 난 숫자 가 배열 길이 의 절반 을 넘 었 다.이 배열 을 정렬 하면 정렬 후 배열 중간 에 있 는 숫자 는 배열 길이 의 절반 이 넘 는 숫자 일 것 이다.즉, 이 숫자 는 통계학 상의 중위 수, 즉 길이 가 n 인 배열 에서 n / 2 번 째 로 큰 숫자 이다.
이런 알고리즘 은 빠 른 정렬 알고리즘 의 계발 을 받는다.무 작위 빠 른 정렬 알고리즘 에서 우 리 는 먼저 배열 에서 무 작위 로 숫자 를 선택 한 다음 에 배열 의 숫자 순 서 를 조정 하여 선택 한 숫자 보다 작은 숫자 를 왼쪽 에 배열 하고 선택 한 숫자 보다 큰 숫자 를 오른쪽 에 배열 합 니 다.만약 이 선택 한 숫자의 아래 표 시 는 n / 2 라면, 이 숫자 는 배열 의 중위 이다.만약 그것 의 아래 표 시 는 n / 2 보다 크다 면, 중위 수 는 그것 의 왼쪽 에 있어 야 한다. 우 리 는 이어서 그것 의 왼쪽 부분의 배열 에서 찾 을 수 있다.만약 그것 의 아래 표 시 는 n / 2 보다 작다 면, 중위 수 는 그것 의 오른쪽 에 있어 야 한다. 우 리 는 이어서 그것 의 오른쪽 부분의 배열 에서 찾 을 수 있다.이것 은 전형 적 인 귀속 과정 이다.
해법 2: 배열 의 특징 에 따라 O (n) 의 알고리즘 을 찾 아 라.
배열 에 나타 난 숫자 가 배열 길이 의 절반 을 넘 는 것 은 다른 모든 숫자 가 나타 난 횟수 보다 더 많다 는 것 이다.따라서 우 리 는 배열 을 옮 겨 다 닐 때 두 개의 값 을 저장 하 는 것 을 고려 할 수 있다. 하 나 는 배열 의 한 숫자 이 고 하 나 는 횟수 이다.우리 가 다음 ~ 숫자 를 옮 겨 다 닐 때 다음 숫자 가 우리 가 이전에 저장 한 숫자 와 같다 면 횟수 는 l 을 추가 합 니 다. 다음 숫자 가 우리 가 이전에 저장 한 숫자 와 다 르 면 횟수 는 1 을 줄 입 니 다.횟수 가 곰팡이 라면 다음 숫자 를 저장 하고 횟수 를 1 로 설정 해 야 한다.우리 가 찾 아야 할 숫자 가 다른 모든 숫자 보다 더 많이 나 오기 때문에 찾 아야 할 숫자 는 마지막 으로 횟수 를 1 시 에 대응 하 는 숫자 로 설정 하 는 것 이 분명 하 다.
구현 코드:
해법 1: Partition 함수 기반 O (n) 알고리즘

/**
                       ，       

 @param numArray      
 @param arrayLength      
 @return      
 */
int findMoreThanHalfNumFirstWay(int *numArray, int arrayLength) {
    if(numArray == NULL){
        return -1;
    }
    if (arrayLength == 0) {
        return -1;
    }
    
    NSInteger startIndex = 0;
    NSInteger endIndex = arrayLength - 1;
    int compareValue = numArray[startIndex];
    while (startIndex < endIndex) {
        //           compareValue   
        while (startIndex < endIndex && numArray[endIndex] > compareValue) {
            endIndex --;
        }
        numArray[startIndex] = numArray[endIndex];
        
        //           compareValue   
        while (startIndex < endIndex && numArray[startIndex] < compareValue) {
            startIndex++;
        }
        numArray[endIndex] = numArray[startIndex];
    }
    
    numArray[startIndex] = compareValue;
    return numArray[arrayLength/2];
}

해법 2: 배열 의 특징 에 따라 O (n) 의 알고리즘 을 찾 아 라.

/**
                       ，       
 
 @param numArray      
 @param arrayLength      
 @return      
 */
int findMoreThanHalfNumSecondWay(int *numArray, int arrayLength) {
    if(numArray == NULL){
        return -1;
    }
    if (arrayLength == 0) {
        return -1;
    }
    //      
    int numCount = 1;
    //            
    int halfNum = numArray[0];
    for (int tmpIndex = 1; tmpIndex < arrayLength; tmpIndex++) {
        if (numArray[tmpIndex] == halfNum) {
            numCount ++;
        }
        else {
            numCount --;
            if (numCount == 0) {
                halfNum = numArray[tmpIndex];
                numCount = 1;
            }
        }
    }
    
    return halfNum;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        //                  
        int numbers[] = {1, 2, 3, 2, 2, 2, 5, 0, 2};
        printf("%d", findMoreThanHalfNumFirstWay(numbers, 9));
        printf("
");
        printf("%d", findMoreThanHalfNumSecondWay(numbers, 9));
        printf("
");
    }
    return 0;
}