資訊專(zhuān)欄INFORMATION COLUMN
摘要：寫(xiě)在前面今天的小李的目標(biāo)是排序算法，果然還是要下手寫(xiě)才會(huì)更有體會(huì)，也更記得住。排序算法冒泡排序主要是比對(duì)相鄰兩個(gè)數(shù)之間的大小關(guān)系，不斷將較大值交換至最后。
寫(xiě)在前面
今天的小李的目標(biāo)是排序算法，果然還是要下手寫(xiě)才會(huì)更有體會(huì)，也更記得住。
認(rèn)真做題的分割線(xiàn)215. 數(shù)組中的第K個(gè)最大元素
難度：中等
在未排序的數(shù)組中找到第k個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第k個(gè)最大的元素，而不是第k個(gè)不同的元素。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4
說(shuō)明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。
我的題解:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
num = quicksort(nums,0,len(nums)-1)
return num[len(nums)-k]
def quicksort(v,start,end):
if start < end:
i,j = start,end
base = v[i]
while i < j:
while i < j and v[j] >= base:
j -= 1
v[i] = v[j]
while i < j and v[i] < base:
i +=1
v[j] = v[i]
v[i] = base
quicksort(v,start,i-1)
quicksort(v,j+1,end)
return v
我的思路:
通過(guò)快速排序算法,對(duì)數(shù)據(jù)進(jìn)行排序后,找到對(duì)應(yīng)的值.
排序算法:
快排的主體思路是,找到對(duì)應(yīng)的標(biāo)桿值,然后對(duì)標(biāo)桿值兩側(cè)進(jìn)行劃分,然后分而治之,對(duì)兩側(cè)再進(jìn)行遞歸的切分標(biāo)桿值.
所以常見(jiàn)的是遞歸的思路.
之前看《算法圖解》的代碼，今晚嘗試了下：
def quicksort(array):
if len(array) < 2:
return array
temp = array[0]
less = [ i for i in array[1:] if i <= temp]
greater = [i for i in array[1:] if i > temp]
return quicksort(less) + temp + quicksort(greater)
比較能夠明顯的顯示快排的思路，但是這個(gè)效率并不高，因?yàn)槊看芜f歸都需要對(duì)兩側(cè)的數(shù)組進(jìn)行一次硬性排序。
且return 不支持不同類(lèi)型（list和int）一起。
優(yōu)化后，我們采用的方式是加入了start和end的參數(shù)，依然是對(duì)標(biāo)桿值兩側(cè)進(jìn)行劃分，但是會(huì)減少排序重復(fù)量，降低了復(fù)雜度。
215. 數(shù)組中的第K個(gè)最大元素
難度：中等
給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前k高的元素。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
說(shuō)明：
你可以假設(shè)給定的k總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)。
你的算法的時(shí)間復(fù)雜度必須優(yōu)于O(n log n), n 是數(shù)組的大小。
我的題解:
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
l = dict()
res = []
for i in nums:
if i in l:
l[i] += 1
else:
l[i] = 1
items = list(l.items())
items.sort(key = lambda x:x[1],reverse = True)
for i in range(k):
res.append(items[i][0])
return res
我的思路:
這題按正常題解，應(yīng)該使用桶排序。
我用的方案是用hash表記錄對(duì)應(yīng)的值，然后將hash表轉(zhuǎn)成二維list，并對(duì)二級(jí)域進(jìn)行排序。
然后輸出對(duì)應(yīng)值。
其他:
這題要再?lài)L試下桶排序的方式，主要是對(duì)sort()函數(shù)參數(shù)有了新的認(rèn)識(shí)。
sorted(iterable[, cmp[, key[, reverse]]])
iterable指定要排序的list或者iterable
cmp為函數(shù)，指定排序時(shí)進(jìn)行比較的函數(shù)，可以指定一個(gè)函數(shù)或者lambda函數(shù)
key為函數(shù)，指定取待排序元素的哪一項(xiàng)進(jìn)行排序，用于指定哪一個(gè)域
215. 數(shù)組中的第K個(gè)最大元素
難度：中等
給定一組非負(fù)整數(shù)，重新排列它們的順序使之組成一個(gè)最大的整數(shù)。
示例 1:
輸入: [10,2]
輸出: 210
示例 2:
輸入: [3,30,34,5,9]
輸出: 9534330
說(shuō)明: 輸出結(jié)果可能非常大，所以你需要返回一個(gè)字符串而不是整數(shù)。
我的題解:
class Solution(object):
def largestNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
l = len(nums)
i = l
#比較a+b 和 b+a
while i > 0:
for j in range(i-1):
a = nums[j]
b = nums[j+1]
ab = int(str(a)+str(b))
ba = int(str(b)+str(a))
if ab < ba:
nums[j],nums[j+1] = nums[j+1],nums[j]
i -=1
res= ""
for n in nums:
if res == "" and n == 0:
continue
res += str(n)
if res == "":
return "0"
return res
我的思路:
這題參考了小佳揚(yáng)的寫(xiě)法，主要是使用了冒泡排序。
但屬于自定義的冒泡排序，每次都比對(duì)字符串前后排序不同時(shí)得出的結(jié)果哪個(gè)更大，會(huì)獲得的更大值需要放在更前，相反則放后。
排序算法:
冒泡排序主要是比對(duì)相鄰兩個(gè)數(shù)之間的大小關(guān)系，不斷將較大值交換至最后。
明天要繼續(xù)攻略排序算法。
紙上得來(lái)終覺(jué)淺，絕知此事要躬行。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43661.html
摘要：刷題第三天正式刷題第三天。注意空字符串可被認(rèn)為是有效字符串。錯(cuò)誤的一次是因?yàn)闆](méi)有考慮空字符串，當(dāng)存在為的時(shí)候，結(jié)果應(yīng)該為。第二題加一難度簡(jiǎn)單類(lèi)型給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。 刷題第三天 正式刷題第三天。之前看了個(gè)說(shuō)法，挺認(rèn)可的。就是不要太在意一天的能呈現(xiàn)的價(jià)值，但是要在意累計(jì)的價(jià)值。之前很多時(shí)候我會(huì)對(duì)今天一天沒(méi)有完成的計(jì)劃而沮喪，事實(shí)上，算法的實(shí)踐...
摘要：第五題對(duì)稱(chēng)二叉樹(shù)難度簡(jiǎn)單給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱(chēng)的。第十六題最大連續(xù)的個(gè)數(shù)難度簡(jiǎn)單給定一個(gè)二進(jìn)制數(shù)組，計(jì)算其中最大連續(xù)的個(gè)數(shù)。第十八題平方數(shù)之和難度簡(jiǎn)單給定一個(gè)非負(fù)整數(shù)，你要判斷是否存在兩個(gè)整數(shù)和，使得。 寫(xiě)在前面 最近忙著調(diào)教新裝備，沒(méi)有及時(shí)的寫(xiě)題解，但是沒(méi)有在偷懶沒(méi)刷題喔~來(lái)認(rèn)真整理下最近做的題目~ 之前考慮按tag來(lái)刷題，后來(lái)收到了推薦的leetcode題解，就根據(jù)上...
摘要：寫(xiě)在前面的話(huà)好幾天木有刷題啦，今天猛刷了一把，要梳理一個(gè)順序好好的學(xué)習(xí)啦一定要好好執(zhí)行每天做題的計(jì)劃最近真的好忙碌啊，還要做視頻。第二題最大子序和難度簡(jiǎn)單給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最大和的連續(xù)子數(shù)組子數(shù)組最少包含一個(gè)元素，返回其最大和。 寫(xiě)在前面的話(huà) 好幾天木有刷題啦，今天猛刷了一把，要梳理一個(gè)順序好好的學(xué)習(xí)啦~一定要好好執(zhí)行每天做題的計(jì)劃！最近真的好忙碌啊，還要做視頻。不過(guò)呢，看...
摘要：寫(xiě)在前面今天沒(méi)有叨逼叨但是又一次錯(cuò)過(guò)了競(jìng)賽愛(ài)睡覺(jué)的小李下周要上班，下下周一定要參加了握拳認(rèn)真做題的分割線(xiàn)第一題兩地調(diào)度公司計(jì)劃面試人。第人飛往市的費(fèi)用為，飛往市的費(fèi)用為。示例輸入輸出解釋第一個(gè)人去市，費(fèi)用為。 寫(xiě)在前面 今天沒(méi)有叨逼叨...但是又一次錯(cuò)過(guò)了競(jìng)賽...愛(ài)睡覺(jué)的小李...下周要上班，下下周一定要參加了（握拳 認(rèn)真做題的分割線(xiàn) 第一題 1029. 兩地調(diào)度公司計(jì)劃面試2N人。...
摘要：第二題漢明距離難度簡(jiǎn)單兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目。給出兩個(gè)整數(shù)和，計(jì)算它們之間的漢明距離。第三題買(mǎi)賣(mài)股票的最佳時(shí)機(jī)難度簡(jiǎn)單給定一個(gè)數(shù)組，它的第個(gè)元素是一支給定股票第天的價(jià)格。 寫(xiě)在前面 這幾天斷斷續(xù)續(xù)做了題目，也在慢慢體會(huì)一些數(shù)據(jù)思維。終于不用邊做視頻邊寫(xiě)題目啦~開(kāi)心~把這幾天的題解發(fā)一下~ 認(rèn)真做題的分割線(xiàn) 第一題 977. 有序數(shù)組的平方難度...
閱讀 2267·2021-11-15 11:39
閱讀 1035·2021-09-26 09:55
閱讀 970·2021-09-04 16:48
閱讀 2908·2021-08-12 13:23
閱讀 956·2021-07-30 15:30
閱讀 2494·2019-08-29 14:16
閱讀 922·2019-08-26 10:15
閱讀 559·2019-08-23 18:40
