Re: [閒聊] 每日leetcode已回收

看板Marginalman作者sixB (6B)時間1年前 (2024/07/26 04:15)推噓2(2推 0噓 4→)

留言6則, 3人參與討論串566/1554 (看更多)

前幾天就寫merge 想說今天寫一下quick ㄇㄉ真的TLE== 來玩radix好了 ※ 引述《sustainer123 (caster)》之銘言： : ※ 引述《DJYOMIYAHINA (通通打死)》之銘言： : : 肥肥想說來練一下quick : : 然後怎麼搞都過不了worst case : : 直接水桶伺候操 : : 後來想想我最該練的應該是merge sort : : 沒寫過幾次 : : def sortArray(self, nums: List[int]) -> List[int]: : : cnt = [0 for _ in range(100002)] : : for n in nums: : : cnt[n+50000] += 1 : : ans = [] : : for idx, val in enumerate(cnt): : : for i in range(val): : : ans.append(idx-50000) : : return ans : : # def middle_of_threerandom(l, r): : : # pivot_index_0 = random.randint(l, r) : : # pivot_index_1 = random.randint(l, r) : : # pivot_index_2 = random.randint(l, r) : : # tmp = sorted([(nums[pivot_index_0], pivot_index_0), : : (nums[pivot_index_1], pivot_index_1), (nums[pivot_index_2], pivot_index_2)]) : : # return tmp[1][1] : : # def qs(l,r): : : # if l >= r: : : # return : : # pivot_idx = middle_of_threerandom(l,r) : : # nums[r], nums[pivot_idx] = nums[pivot_idx], nums[r] : : # pivot = nums[r] : : # start = l : : # for i in range(l, r): : : # if nums[i] <= pivot: : : # nums[start], nums[i] = nums[i], nums[start] : : # start += 1 : : # nums[r], nums[start] = nums[start], nums[r] : : # qs(l, start-1) : : # qs(start+1, r) : : # qs(0, len(nums)-1) : : # return nums : 思路: : 本來想說quick sort : 結果翻一下書才發現quick sort最糟狀況會n**2 : 能用的就heap sort跟merge sort : 剛好複習一下排序 : 不然平常都sort() 啟動 : Python Code: : class Solution: : def sortArray(self, nums: List[int]) -> List[int]: : def merge(left: int,mid: int,right: int): : tmp = [0] *((right - left) + 1) : i,j,k = left, mid + 1, 0 : while i <= mid and j <= right: : if nums[i] <= nums[j]: : tmp[k] = nums[i] : i += 1 : else: : tmp[k] = nums[j] : j += 1 : k += 1 : while i <= mid: : tmp[k] = nums[i] : i += 1 : k += 1 : while j <= right: : tmp[k] = nums[j] : j += 1 : k += 1 : for k in range(len(tmp)): : nums[left+k] = tmp[k] : def merge_sort(nums: list[int],left: int,right: int): : if left >= right: : return : mid = (left + right) // 2 : merge_sort(nums,left,mid) : merge_sort(nums,mid+1,right) : merge(left,mid,right) : merge_sort(nums,0,len(nums)-1) : return nums -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721938543.A.E49.html

→

sixB

07/26 04:15, 1年前 , 1^F

07/26 04:15, 1^F

→

sixB

07/26 04:16, 1年前 , 2^F

07/26 04:16, 2^F

→

sixB

07/26 04:16, 1年前 , 3^F

07/26 04:16, 3^F