# 描述

在一個(gè)長(zhǎng)度為 n+1 的數(shù)組中所有的數(shù)字都在 1~n 范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的。
請(qǐng)至少找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。

# 思路

采用二分法查找，時(shí)間復(fù)雜度為 O(nlogn)

在數(shù)字 1~n 中取中間值 m = (1+n) / 2, 此時(shí)數(shù)字包括 1~m, m+1~n 兩段；
遍歷數(shù)組，獲得數(shù)字 1~m 的個(gè)數(shù);
如果數(shù)字 1~m 的個(gè)數(shù)大于 m，說(shuō)明 1~m 這一段內(nèi)肯定有重復(fù)數(shù)字，那么在這一段內(nèi)繼續(xù)取中間值比較；
如果數(shù)字 1~m 的個(gè)數(shù)等于 m，這一段不一定有重復(fù)數(shù)字，比較后一段；
如果數(shù)字 1~m 的個(gè)數(shù)小于 m，說(shuō)明 m+1~n 這一段一定有重復(fù)數(shù)字，在后一段取中間值比較；
按照上述方法一直取中間值比較，直到只剩一個(gè)數(shù)字且這個(gè)數(shù)字出現(xiàn)次數(shù)超過(guò) 1 ，該數(shù)字即為重復(fù)數(shù)字

# 解決

def find_dux_num(seq):
    if len(seq) <= 1 or seq is None:
        return None

    start, end = 1, len(seq) - 1  # 獲取數(shù)字1，n

    while start <= end:
        mid = (start+end) // 2  # 獲取中間數(shù)字
        count = count_num(seq, start, mid)  # 計(jì)算[start, mid]數(shù)字之間的數(shù)目

        # 當(dāng)只取到一個(gè)數(shù)字時(shí)，如果該數(shù)字出現(xiàn)數(shù)目大于1，就是重復(fù)數(shù)字
        if start == end:
            if count > 1:
                return start
            else:
                break

        # 如果count數(shù)目 > 中間數(shù)字到起始數(shù)字之差，一定存在重復(fù)數(shù)字，繼續(xù)在這一段中求中間數(shù)比較
        if count > mid - start + 1:
            end = mid
        # 否則在后一段中求中間數(shù)比較
        else:
            start = mid + 1

    return None


def count_num(seq, start, end):
    count = 0
    for i in seq:
        if start <= i <= end:
            count += 1
    return count


if __name__ == '__main__':
    print(find_dux_num([1, 2, 3, 4, 3]))