class Solution:
? ? def duplicate(self , numbers: List[int]) -> int:
? ? ? ? if len(numbers) <= 1:
? ? ? ? ? ? return -1
? ? ? ? import collections
? ? ? ? num_dict = collections.Counter(numbers)
? ? ? ? res = [key for (key,value) in num_dict.items() if value > 1]
? ? ? ? return res[0]
class Solution:
? ? def sort(self,num): #快排
? ? ? ? if len(num) <= 1:
? ? ? ? ? ? return num
? ? ? ? import random
? ? ? ? pivot = random.choice(num)
? ? ? ? left = self.sort([i for i in num if i < pivot])
? ? ? ? right = self.sort([i for i in num if i > pivot])
? ? ? ? same = [i for i in num if i == pivot]
? ? ? ? return left+same+right
? ? def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
? ? ? ? if k > len(input) or k == 0: #對數(shù)據(jù)進行錯誤判斷
? ? ? ? ? ? return []
? ? ? ? res = self.sort(input)
? ? ? ? return res[:k]
?#插入排序
class Solution:
? ? def __init__(self) -> None:
? ? ? ? self.res = []
? ? def Insert(self, num): #插入排序
? ? ? ? if len(self.res) == 0:
? ? ? ? ? ? self.res.append(num)
? ? ? ? else:
? ? ? ? ? ? i = 0
? ? ? ? ? ? while i < len(self.res):
? ? ? ? ? ? ? ? if num <= self.res[i]:
? ? ? ? ? ? ? ? ? ? break
? ? ? ? ? ? ? ? i += 1
? ? ? ? ? ? self.res.insert(i,num)
? ? def GetMedian(self):
? ? ? ? n = len(self.res)
? ? ? ? if n % 2 == 0:
? ? ? ? ? ? return (self.res[n//2]+self.res[n//2-1])/2.0
? ? ? ? else:
? ? ? ? ? ? return self.res[n//2]
class Solution:
? ? def merge(self,num): #使用類似于快排的方式
? ? ? ? if len(num) <= 1:
? ? ? ? ? ? return 0
? ? ? ? bigger = []? #比基準(zhǔn)大的數(shù)字
? ? ? ? smaller = [] #比基準(zhǔn)小的數(shù)字
? ? ? ? prev = num[0] #選取第一個數(shù)作為基準(zhǔn)
? ? ? ? res = 0
? ? ? ? for i in num[1:]: #遍歷剩下的數(shù)組
? ? ? ? ? ? if i > prev: #如果大于基準(zhǔn)（不是逆序?qū)Γ?/span>
? ? ? ? ? ? ? ? bigger.append(i) #放到bigger中
? ? ? ? ? ? else: #是逆序?qū)?/span>
? ? ? ? ? ? ? ? smaller.append(i) #放到smaller中，此時對于small中的每一個數(shù)，逆序?qū)Χ贾辽俚扔赽igger中的個數(shù)（不考慮smaller內(nèi)部情況）
? ? ? ? ? ? ? ? res += len(bigger) + 1 if num[i] < prev else len(bigger) #如果嚴(yán)格不等值，就得加上基準(zhǔn)，否則不加
? ? ? ? return res+self.merge(bigger)+self.merge(smaller) #遞歸去查看bigger和smaller中的情況
? ? def InversePairs(self , nums: List[int]) -> int:文章來源：http://www.zghlxwxcb.cn/news/detail-637664.html
? ? ? ? return self.merge(nums)%1000000007文章來源地址http://www.zghlxwxcb.cn/news/detail-637664.html
到了這里，關(guān)于《劍指offer》（3）排序算法篇的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
