首頁 Leetcode

(Leetcode基礎系列) Python內建排序sorted()

前言

大家可能在剛學習程式語言的時候，想要挑戰一些程式小題目，那排序的題目往往是最經典的一類型題目了。

那今天要來介紹一個題目偷雞的Python的內建函式sorted()

功能

sorted()將可迭代物件適條件情況進行排序,簡單來說就是可以讓List,Dict這類能放多種資料的結構進行排序

基本用法

由小到大排列

sorted(可迭代物件)

1
2
listA =[1,5,6,7,1,23]
print(sorted(listA))# 印出[1, 1, 5, 6, 7, 23]

可以看到陣列內容被由小到大排列了

由大到小排列

sorted(可迭代物件,reverse=True)

1
2
listA =[1,5,6,7,1,23]
print(sorted(listA,reverse=True))# 印出[23, 7, 6, 5, 1, 1]

進階用法

指定排序優先條件 sorted(可迭代物件,key=排序優先條件)

1
2
3
listA = [[1,3],[2,6],[8,10],[15,18],[4,8]]
print(sorted(listA,key=lambda i: i[0]))# 根據陣列的第一個值進行排列
# 印出 [[1, 3], [2, 6], [4, 8], [8, 10], [15, 18]]

當然也可以反過來，同樣的加入reverse=True就可以了

實作挑戰

試試看使用sorted()函數來解Leetcode演算法題目

Leetcode.56 Merge Intervals(Medium)
Leetcode.57 Insert Interval(Medium)

解答

Leetcode.56 Merge Intervals

1
2
3
4
5
6
7
8
9
class Solution:
    def merge(self, intervals):
        ans = []
        for i in sorted(intervals, key=lambda i: i[0]):
            if ans and i[0] <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], i[1])
            else:
                ans.append(i),
        return ans

解釋: 首先題目要求把重疊的區域合併起來，那本次的做法是

  1. 將intervals陣列先透過sorted()對第一個值進行排序，這個效果可以將排序的工作更來簡便(減少對intervals內部第一個值順序異常的問題)
  2. 檢驗每個當前陣列元素i 是否超過目前ans(回傳答案)得最大值，如過超過去更新最大值
  3. 若沒有超過直接加入至ans答案陣列(代表符合排序條件)
  4. 回傳 結束

Leetcode.57 Insert Interval

基本上相同 只是參數不同

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def insert(self, intervals: [[int]], newInterval: [int]) -> [[int]]:
        intervals.append(newInterval)
        out = []
        for i in sorted(intervals, key=lambda i: i[0]):
            print(out)
            if out and i[0] <= out[-1][1]:
                out[-1][1] = max(out[-1][1], i[1])
            else:
                out += i,
        return out

多一個在sorted()排序前將需要插入的資料補進intervals