首頁 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