수조에 나타나는 횟수가 절반 이상인 숫자를 구하다

1638 단어
def partition(data,start,last):
    if data is None:
        return None
    if start < 0 or last < 0:
        return None
    if last <= start:
        return start

    mid_num = data[start]
    while start < last:
        while start < last and  mid_num <= data[last]:
            last -= 1

        data[start] = data[last]

        while start < last and data[start] <= mid_num:
            start += 1

        data[last] = data[start]

    data[start] = mid_num
    return start


def find_kth_num(data,k):
    if data is None:
        return None

    if k >= len(data):
        return None

    start = 0
    last = len(data) - 1
    index = partition(data,start,last)

    while index != k:
        if k < index:
            last = index - 1
            index = partition(data,start,last)
        else:
            start = index + 1
            index = partition(data,start,last)

    return data[k]


def more_than_half_num(data):
    elem =  find_kth_num(data,len(data)//2)

    cnt = 0
    for _ in data:
        if _ == elem:
            cnt += 1

    if cnt > len(data)//2:
        return elem
    else:
        return None

def main():
    data = [5,4,2,2,2]
    num = more_than_half_num(data)
    print(num)

해법 2:
def more_than_half_num2(data):
    num = None
    times = 0

    for item in data:
        if times == 0:
            num = item
            times = 1
        elif num == item:
            times += 1
        elif num != item:
            times -= 1

    if times > 0:
        return num
    else:
        return None

좋은 웹페이지 즐겨찾기