검지offer 제2판(Python3)-면접문제 39:수조에 나타난 횟수가 절반을 넘는 숫자

제2장 면접에 필요한 기초 지식

제3장 고품질 코드

제4장 면접 문제 해결의 사고방식

면접 문제 27: 두 갈래 나무의 거울

면접 문제 29: 시계 방향 인쇄 매트릭스

면접 문제 30:min 함수를 포함하는 창고

면접 문제 31: 창고의 압입, 팝업 서열

면접 문제

면접 문제 33: 두 갈래 검색 트리의 뒷순서 반복 서열

면접 문제 34: 두 갈래 나무와 어떤 값의 경로

면접 문제

면접 문제 36: 두 갈래 검색 트리와 양방향 체인 테이블

면접 문제 38: 문자열의 배열

제5장 시간과 공간 효율 최적화

제6장 면접에서의 각종 능력

제7장 두 가지 면접 사례

제목 설명
  수조 중 한 숫자가 수조의 길이의 절반을 초과하는 횟수가 있으니 이 숫자를 찾아내세요.예를 들어 길이가 9인 그룹 {1,2,3,2,2,5,4,2}를 입력하십시오.숫자 2는 수조에 5차례나 나타나 수조의 길이의 절반을 초과하기 때문에 출력 2.존재하지 않으면 0을 출력합니다.
문제 풀이 사고방식 우객망 방법 1: 미뢰수조 중 한 숫자가 수조의 길이의 절반을 초과하기 때문에 그 숫자가 다른 숫자보다 더 많이 나타난다.그룹을 훑어볼 때 두 개의 값을 저장하는 것을 고려하십시오. 하나는 그룹의 한 숫자이고, 다른 하나는 횟수입니다.   우리가 다음 숫자를 훑어볼 때, 다음 숫자가 우리가 이전에 저장한 숫자와 같다면, 횟수는 1을 더한다.다르면 횟수가 1 줄어든다.횟수가 0이면 다음 숫자를 저장하고 횟수를 1로 설정해야 합니다.이렇게 찾는 숫자는 마지막으로 횟수를 1로 설정할 때 대응하는 숫자일 수도 있고, 이 숫자가 그룹에 있는 수량을 통계해야 확인할 수 있다.실전

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        length = len(numbers)
        i = 0
        counts = 0
        while i < length:
            if counts == 0:
                digit = numbers[i]
                i += 1
                counts = 1
                continue
            if numbers[i] != digit:
                counts -= 1
            else:
                counts += 1
            i += 1
        
        counts = 0
        for num in numbers:
            if num == digit:
                counts += 1
        if counts > length >> 1:
            return digit
        return 0

방법2:   는 빠른 정렬 계발을 받아 성숙한 수조 중 임의의 k대 숫자를 얻을 수 있는 알고리즘이 있고 시간 복잡도는 O(n)이다.만약 수조에 수량이 수조의 길이의 절반을 초과한다면 정렬된 수조의 중간 위치의 수는 반드시 그 수량이 절반을 초과한 수이기 때문에 이 문제는 정렬된 수조의 중간 위치수를 찾는 것으로 설명할 수 있다.우리는 먼저 무작위로 숫자를 선택한 다음에 수조의 순서를 조정하여 선택한 숫자보다 큰 숫자는 오른쪽에 있고 작은 숫자는 왼쪽에 있다.만약 선택한 수의 색인이 n/2이면 이 수는 중간 위치수입니다.만약 그 인덱스가 n/2보다 크면 중간 위치는 이 수의 왼쪽에 있고 계속 왼쪽 그룹으로 가서 찾습니다.그렇지 않으면 중간 위치가 오른쪽에 있고, 계속 오른쪽 그룹으로 가서 찾아라.이것은 전형적인 귀속 과정이다.실전

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return numbers
        
        def recc(begin, end):
            if begin >= end:
                return numbers[begin]
            index = begin
            for i in range(begin+1, end+1):
                if numbers[index] > numbers[i]:
                    numbers[index], numbers[i] = numbers[i], numbers[index]
                    index = i 
            if index == length >> 1:
                return numbers[index]
            if index > length >> 1:
                num = recc(begin, index-1)
            else:
                num = recc(index+1, end)
            return num
        
        length = len(numbers)
        number = recc(0, length-1)
        counts = 0
        for i in range(length):
            if number == numbers[i]:
                counts += 1
        if counts > length >> 1:
            return number
        return 0