要求：列表中有1000000個(gè)元素，取值范圍是[1000, 10000)，設(shè)計(jì)一個(gè)函數(shù)找出列表中的重復(fù)元素。
def find_dup(items: list): dups = [0] * 9000 for item in items: dups[item - 1000] += 1 for idx, val in enumerate(dups): if val > 1: yield idx + 1000
點(diǎn)評(píng)：這道題的解法和計(jì)數(shù)排序的原理一致，雖然元素的數(shù)量非常多，但是取值范圍[1000, 10000)并不是很大，只有9000個(gè)可能的取值，所以可以用一個(gè)能夠保存9000個(gè)元素的dups列表來(lái)記錄每個(gè)元素出現(xiàn)的次數(shù)，dups列表所有元素的初始值都是0，通過(guò)對(duì)items列表中元素的遍歷，當(dāng)出現(xiàn)某個(gè)元素時(shí)，將dups列表對(duì)應(yīng)位置的值加1，最后dups列表中值大于1的元素對(duì)應(yīng)的就是items列表中重復(fù)出現(xiàn)過(guò)的元素。
京公網(wǎng)安備 11010802030320號(hào)