chapter16-sort-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 1.5k | Reading time ≈ 6

chapter16-sort-algorithm

[TOC]

排序类算法

1.堆 快速选择
1. Kth Element

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# 215. 数组中的第K个最大元素
def findKthLargest(nums, k: int ) -> int:
    # 有题意可知
    # 获得数组中第K大的元素
    # 意思就是排序(降序)后，第K个位置大的数

    # 直接排序 直接取第k个位置的数
    def solve1():
        nums.sort() #默认降序 升序反转一下即可reverse = True
        return nums[ -k ]

    # 维持最大堆，就是保持堆的长度为k，而堆顶总是当前堆里的最大值，如果后面值比堆定大，
    # 且堆长度大于k需要更新堆定值即可，遍历完最后的值为第k大元素
    def solve2():
        import queue
        dp = queue.PriorityQueue()
        for v in nums:
            dp.put(v)
            if dp.qsize() > k:
                dp.get()

        return dp.get()

    # 利用快速排序方法，求解第K个元素
    # 本次是根据传入数组的第一个元素作为哨兵(left)进行比较分离的，就是dp[left]作为中心点，
    # 把数组中的数分为小于和大于它的数为了两部分(一左一右) 如partition第一次nums的结果
    # nums = [3,2,1,5,6,4]--> [1,2,4,5,6,4] 由于left和right两个指针只在5的时候相遇，
    # 所以只与于3(最左点left)与1(j指针)交换结束第一次分区运算
    # 由如二分法，通过每次选的哨兵进行判断第K个元素属于左还是右，一次往下遍历
    # 直止len(nums) - k的位置，就是要找的第K个元素
    # 其实你不用把它理解为快速选择排序的结果，直接理解为两指针构建二分法处理，
    # 而哨兵就是二分法的mid，因为他的唯一可以确定位置的元素
    # 代码逻辑如下
    def solve3():
        def partition( dp, left, right ):
            i, j = left, right
            while True:
                while dp[ i ] <= dp[ left ] and i < right: i += 1
                while dp[ j ] >= dp[ left ] and j > left: j -= 1
                if i >= j: break
                dp[ i ], dp[ j ] = dp[ j ], dp[ i ]
            dp[ left ], dp[ j ] = dp[ j ], dp[ left ]
            return j

        kk = len(nums) - k
        left, right = 0, len(nums) - 1
        while left < right:
            j = partition(nums, left, right)
            if j == kk:
                break
            elif j < kk:
                left = j + 1
            else:
                right = j - 1

        return nums[ kk ]
nums = [3,2,1,5,6,4];k = 2
findKthLargest(nums, k)
1. 桶排序
1. 出现频率最多的 k 个元素

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def topKFrequent(nums, k):

    # you题意可知
    # 需要出现频率前 k 高的元素。
    # 因此需要对数组每一个数进行求频次，因此直观想法，
    # 就是利用字典对对数组求值(key)与频次(value)
    # 然后通过value排序，取出前k高的元素即可
    # 代码逻辑如下：
    from collections import Counter
    def solve1():
        dp = Counter(nums)
        dp = sorted(dp.items(), key = lambda x:x[ 1 ])
        res = [ ky for ky, v in dp ]
        return res[ -k: ]

    # 优化，统计好数组每一个元素的频次后，
    # 然后通过频次建立桶
    # 意思就是频次作为一个列表的下标，而列表下标对应的值就是当前频次的key
    # 意味着不用O(nlgn)排序时间，直接用O(n)的时间去遍历，因为桶下标的遍历就是顺序的
    # 但意味着空间复杂度的增加
    # 因此你可以使用有序字典进行存储优化
    # 代码逻辑如下：
    def solve2(nums, k):
        l, dp = len(nums), Counter(nums)
        buckets = [None for i in range(l + 1)]
        for key, v in dp.items():
            if not buckets[v]:
                buckets[v] = [key]
            else:
                buckets[v].append(key)
        print(buckets)
        res = []
        for i in range(l, -1, -1):
            if not buckets[i]:
                continue
            if k >= len(buckets[i]):
                res.extend(buckets[i])
                k -= len(buckets[i])
            else:
                res.extend(buckets[i][:k])

        print(res)
        return res
    solve2(nums, k)

nums = [1,1,1,2,2,3]; k = 2
topKFrequent(nums, k)
2. 按照字符出现次数对字符串排序

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def frequencySort(s: str) -> str:
    # you题意可知
    # 需要出现频率前 k 高的元素。
    # 因此需要对数组每一个数进行求频次，因此直观想法，
    # 就是利用字典对对数组求值(key)与频次(value)
    # 然后通过value排序，取出前k高的元素即可
    # 代码逻辑如下：
    from collections import Counter
    def solve1():
        dp = Counter(s)
        dp = sorted(dp.items(), key = lambda x:x[ 1 ], reverse = True)
        res = [ ky * v for ky, v in dp ]
        return ''.join(res)

    # 优化，统计好数组每一个元素的频次后，
    # 然后通过频次建立桶
    # 意思就是频次作为一个列表的下标，而列表下标对应的值就是当前频次的key
    # 意味着不用O(nlgn)排序时间，直接用O(n)的时间去遍历，因为桶下标的遍历就是顺序的
    # 但意味着空间复杂度的增加
    # 因此你可以使用有序字典进行存储优化
    # 代码逻辑如下：
    def solve2():
        l, dp = len(s), Counter(s)
        buckets = [ None for i in range(l + 1) ]
        for key, v in dp.items():
            if not buckets[ v ]:
                buckets[ v ] = [ key*v ]
            else:
                buckets[ v ].append(key*v)
        print(buckets)
        res = [ ]
        for i in range(l, -1, -1):
            if not buckets[ i ]:
                continue
            res.extend(buckets[i])
        print(res)
        return ''.join(res)
    solve2()

s = "Aabb"
frequencySort(s)
1.荷兰国旗问题
1.按颜色进行排序

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def sortColors( nums):
    # you题意可知
    # 直观感受直接用计数排序实现，直接ok，但是要原地修改(当然也行，但是要变量两次)
    # 所以思考直接通过元素之间交换，能否完成
    # 因为0,1,2数字是有相对顺序的，0必须在前面，1中间，2后面且数字一定
    # 所以能够通过三个指针进行逐渐推进呢？
    # 当然是可以的
    # 主要思想是通过zero和two两个指针指向-1，通过one指向0，依次遍历
    # 如果满足one=0|2就依次推进one和two的指针，就能够保证头和尾都是0|1了。
    # 因此代码逻辑如下：
    zero, one, two = -1, 0, len(nums)
    while one < two:
        if nums[ one ] == 0:
            zero += 1
            nums[ zero ], nums[ one ] = nums[ one ], nums[ zero ]
            one += 1
        elif nums[ one ] == 2:
            two -= 1
            nums[ one ], nums[ two ] = nums[ two ], nums[ one ]
        else:
            one += 1
    return nums

nums = [2,0,2,1,1,0]
sortColors(nums)