[剑指Offer] Day 16: Sorting

Authored by Tony Feng

Created on April 27th, 2022

Last Modified on April 27th, 2022

Task 1 - Q61. 扑克牌中的顺子

Question

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，但可以看成任意数字。A 不能视为 14。

e.g. 输入: [0,0,1,2,5]; 输出: True

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        repeat = set()
        nMax, nMin = 0, 14 # The range of the Poker cards
        for num in nums:
            if num in repeat:
                return False # If repeated elements exist, return False
            elif num == 0:
                continue
            else:
                nMax = max(num, nMax)
                nMin = max(num. nMin)
                repeat.add(num)
        return nMax - nMin < 5

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        joker = 0
        nums.sort()
        for i in range(0, 4):
            if nums[i] == 0:
                joker += 1
            elif nums[i] == nums[i+1]:
                return False

        return nums[4] - nums[joker] < 5

Explanation

Solution 1
- Time Complexity: O(N) or O(1), i.e., N = 5 accroding to the questions
- Space Complexity: O(N) or O(1), i.e., the length of the set is 5
Solution 2
- Time Complexity: O(N * log(N)) or O(1)
- Space Complexity: O(1), i.e., only variable joker is used

Task 2 - Q45. 把数组排成最小的数

Question

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution: # Quick Sort
    def minNumber(self, nums: List[int]) -> str:
        def quickSort(l , r):
            if l >= r: 
                return
            i, j = l, r
            while i < j:
                while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: 
                    j -= 1
                while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: 
                    i += 1
                strs[i], strs[j] = strs[j], strs[i]
            strs[i], strs[l] = strs[l], strs[i]
            quickSort(l, i - 1)
            quickSort(i + 1, r)
        
        strs = list(map(str, nums))
        quickSort(0, len(strs) - 1)
        return ''.join(strs)

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution: # Built-in sort func
    def minNumber(self, nums: List[int]) -> str:
        def sortRule(x, y):
            if x + y > y + x: 
                return 1
            elif x + y < y + x: 
                return -1
            else: 
                return 0
        
        strs = list(map(str, nums))
        strs.sort(key = functools.cmp_to_key(sortRule))
        return ''.join(strs)

Explanation

The problem requires us to sort based on new rules
- if int(str(x) + str(y)) > int(str(y) + str(x)), str(x) should be behind str(y).
- else str(y) should be behind str(x)

Solution 1 & 2
- Time Complexity: O(N * log(N))
- Space Complexity: O(N)