快捷導(dǎo)航

Python面試不修改數(shù)組找出重復(fù)的數(shù)字

更新時(shí)間：2022年05月20日 14:18:32 作者：宇宙之一粟

這篇文章主要為大家介紹了不修改數(shù)組找出重復(fù)的數(shù)字Python實(shí)現(xiàn)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

數(shù)組中重復(fù)的數(shù)字

在上一篇博客中劍指Offer之面試題3: 數(shù)組中重復(fù)的數(shù)字中，其實(shí)能發(fā)現(xiàn)這類(lèi)題目的關(guān)鍵就是一邊遍歷數(shù)組一邊查滿足條件的元素。

然后我們?cè)诓┛?用最復(fù)雜的方式學(xué)會(huì)數(shù)組（Python實(shí)現(xiàn)動(dòng)態(tài)數(shù)組）?這篇博客中介紹了數(shù)組這一結(jié)構(gòu)的本質(zhì)，并自己動(dòng)手實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)數(shù)組。

今天我們介紹一下另一道來(lái)自《劍指Offer》的關(guān)于數(shù)組的面試題——不修改數(shù)組找出重復(fù)的數(shù)字。

不修改數(shù)組找出重復(fù)的數(shù)字

題目二：不修改數(shù)組找出重復(fù)的數(shù)字

給定一個(gè)長(zhǎng)度為 n+1 的數(shù)組里的所有數(shù)字都在 0∼n 的范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的。

請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。

樣例：

給定長(zhǎng)度為8的數(shù)組 nums = [2， 3， 5， 4，3， 2， 6，7]

那么輸出重復(fù)的數(shù)字2或者3

思路

首先我們得關(guān)注到，題目要求是：不修改數(shù)組，然后還是 ?? 返回任意一個(gè)重復(fù)的數(shù)字?? 。所以解題思路相比而言變少了：

1.哈希表：跟上一題一樣，本題也可以創(chuàng)建一個(gè)哈希表，如果原數(shù)組的每個(gè)數(shù)字第一次出現(xiàn)，就把他放到哈希表中去，即原數(shù)組大小為m的數(shù)字應(yīng)該放到哈希表下標(biāo)為m的位置上?？臻g復(fù)雜度是 $O(n)$ 。

2.二分法：那么有沒(méi)有不用空間復(fù)雜度 $O(n)$ 的算法。假設(shè)沒(méi)有重復(fù)數(shù)，那么??1~n?? 之間，每個(gè)數(shù)都只能出現(xiàn)一次。而題目中，這個(gè)數(shù)組至少有一個(gè)數(shù)字重復(fù)，即出現(xiàn)的次數(shù)大于1。

利用二分的思想：把 ??1~n?? 的數(shù)字從中間數(shù)字 m 開(kāi)始分為兩部分，前一半為 1~ m，后面一半為 ??m+1 ~n???，如果 ??1~m?? 中的數(shù)字在數(shù)組中出現(xiàn)的次數(shù)大于 m，那么這一半必定有重復(fù)的數(shù)字；

否則，那么另一部分必定含有重復(fù)數(shù)字。接著我們，繼續(xù)對(duì)含有重復(fù)數(shù)字的區(qū)間一分為二，直到找到重復(fù)的數(shù)字。

思路一：哈希表

def find_duplicated_num(nums):
    """hash_map"""
    hash_map = dict()
    for i, val in enumerate(nums):
        if val in hash_map:
            return val
        hash_map[val] = i
    return False

思路二：二分法

def reduce_inter(nums2, left, right):
    """ """
    mid = (left + right) // 2
    count = 0
    length = len(nums2)
    for i in range(length):
        if (nums2[i] >= left) and (nums2[i] <= mid):
            count += 1
    if count > mid - left + 1:
        return left, mid
    else:
        return mid+1, right


def find_duplicated_num2(nums2):
    left, right = 1, len(nums2) - 1
    while left != right:
        left, right = reduce_inter(nums2, left, right)
    return left

測(cè)試

nums = [2, 3, 5, 4, 3, 2, 6, 7]
# nums_n = [5, 4, 3, 2, 6, 7]
print("思路一測(cè)試結(jié)果: ", find_duplicated_num(nums))
print("思路二測(cè)試結(jié)果: ", find_duplicated_num2(nums))

結(jié)果