Leetcode刷题——数组排序

1
2
3
4
5
6
7
8
9
10
11
def bubbleSort(arr):
    for i in range(len(arr)):
    	flag = FLASE
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
            	arr[j], arr[j + 1] = arr[j + 1], arr[j]
            	flag = TRUE
            if not flag:
            	break   
    return arr

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
def cocktail_sort(iterable):
    '''鸡尾酒排序（英语：Cocktail Sort/Shaker Sort）是冒泡排序的轻微变形，
    它还有很多奇怪的名字，双向冒泡排序 (Bidirectional Bubble Sort)、
    波浪排序 (Ripple Sort)、摇曳排序 (Shuffle Sort)、
    飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort)
    原理：
     1. 对序列向尾部做升序冒泡排序，最大元素沉落尾部。
     2. 对序列向头部做降序冒泡排序，最小元素升到头部。
     3. 交替重复步骤1、2，逐渐缩小无序元素范围，直到没有无序元素。
    时间复杂度：O(n^2)
    稳定性： 稳定
    '''
    for i in range(len(iterable) - 1, 0, -1):
        bubbled = 0

        for j in range(i):
            if iterable[j] > iterable[j + 1]:
                iterable[j], iterable[j + 1] = iterable[j + 1], iterable[j]
                bubbled = 1
        
        for j in range(i, 0, -1):
            if iterable[j] < iterable[j - 1]:
                iterable[j], iterable[j - 1] = iterable[j - 1], iterable[j]
                bubbled = 1

        if not bubbled: break

    return iterable

1
2
3
4
5
6
7
8
9
10
11
12
13
def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录未排序序列中最小数的索引
        min_i = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_i]:
                min_i = j
        # 如果找到最小数，将 i 位置上元素与最小数位置上元素进行交换
        if i != min_i:
            arr[i], arr[min_i] = arr[min_i], arr[i]
            
    return arr

1
2
3
4
5
6
7
8
9
10
11
def insertionSort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i
        while j > 0 and arr[j - 1] > temp:
            arr[j] = arr[j - 1]
            j -= 1
        arr[j] = temp
        
    return arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shellSort(arr):
	size = len(arr)
    gap = size // 2
    
    while gap > 0:
        for i in range(gap, size):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2
    return arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def merge(left_arr, right_arr):
    arr = []
    while left_arr and right_arr:
        if left_arr[0] <= right_arr[0]:
            arr.append(left_arr.pop(0))
        else:
            arr.append(right_arr.pop(0))
    while left_arr:
        arr.append(left_arr.pop(0))
    while right_arr:
        arr.append(right_arr.pop(0))
    return arr

def mergeSort(arr):
    size = len(arr)
    if size < 2:
        return arr
    mid = len(arr) // 2
    left_arr, right_arr = arr[0: mid], arr[mid:]
    return merge(mergeSort(left_arr), mergeSort(right_arr))

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
import random
#随机选取枢纽法优化：pi为low与high之间的随机值；
#还有三数取中、九数取中等方式用于选择pi
def randomPartition(arr: [int], low: int, high: int):
		i = random.randint(low, high)
		arr[i], arr[high] = arr[high], arr[i]
		return partition(arr, low, high)

def partition(arr: [int], low: int, high: int):
	x = arr[high]
	i = low - 1
	for j in range(low, high):
		if arr[j] <= arr[high]:
			i += 1
			arr[i], arr[j] = arr[j], arr[i]
	arr[i + 1], arr[high] = arr[high], arr[i + 1]
	return i + 1

def quickSort(arr, low, high):
	if low < high:
		pi = randomPartition(arr, low, high)
		quickSort(arr, low, pi - 1)
		quickSort(arr, pi + 1, high)

	return arr

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 heapify(arr: [int], index: int, end: int):
	left = index * 2 + 1
	right = left + 1
	while left <= end:
		# 当前节点为非叶子结点
		max_index = index
		if arr[left] > arr[max_index]:
			max_index = left
		if right <= end and arr[right] > arr[max_index]:
			max_index = right
		if index == max_index:
			# 如果不用交换，则说明已经交换结束
			break
		arr[index], arr[max_index] = arr[max_index], arr[index]
		# 继续调整子树
		index = max_index
		left = index * 2 + 1
		right = left + 1

# 初始化大顶堆
def buildMaxHeap(arr: [int]):
	size = len(arr)
	# (size-2) // 2 是最后一个非叶节点，叶节点不用调整
	for i in range((size - 2) // 2, -1, -1):
		heapify(arr, i, size - 1)
	return arr

# 升序堆排序，思路如下：
# 1. 先建立大顶堆
# 2. 让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值
# 3. 再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值
# 4. 以此类推，直到最后一个元素交换之后完毕。
def maxHeapSort(arr: [int]):
	buildMaxHeap(arr)
	size = len(arr)
	for i in range(size):
		arr[0], arr[size-i-1] = arr[size-i-1], arr[0]
		heapify(arr, 0, size-i-2)
	return arr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def countingSort(arr):
    arr_min, arr_max = min(arr), max(arr)
    size = arr_max - arr_min + 1
    counts = [0 for _ in range(size)]
    
    for num in arr:
    	#用数列最小值作为偏移量，计算下标出现次数
        counts[num - arr_min] += 1
    for j in range(1, size):
        counts[j] += counts[j - 1]
    
    res = [0 for _ in range(len(arr))]
    for i in range(len(arr) - 1, -1, -1):
        res[counts[arr[i] - arr_min] - 1] = arr[i]
        counts[arr[i] - arr_min] -= 1
    
    return res  

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
def insertionSort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        j = i
        while j > 0 and arr[j - 1] > temp:
            arr[j] = arr[j - 1]
            j -= 1
        arr[j] = temp
        
    return arr
    
    
def bucketSort(arr, bucket_size = 5):
    arr_min, arr_max = min(arr), max(arr)
    bucket_count = (arr_max - arr_min) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    
    for num in arr:
        buckets[(num - arr_min) // bucket_size].append(num)
        
    res = []
    for bucket in buckets:
        insertionSort(bucket)
        res.extend(bucket)
    
    return res  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def radixSort(arr):
    size = len(str(max(arr)))
    
    for i in range(size):
        buckets = [[] for _ in range(10)]
        for num in arr:
            buckets[num // (10**i) % 10].append(num)
    	arr.clear()
    	for bucket in buckets:
        	for num in bucket:
                arr.append(num)
            
    return arr

1
2
3
4
5
6
7
8
9
10
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        left = 0
        right = 0
        while right < len(nums):
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

1
2
3
4
5
6
7
8
class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        awards = medals + [str(i+1) for i in range(3,len(score))]
        score_to_award = {s:a for s,a in zip(sorted(score,reverse=True),awards)}
        res = [score_to_award[s] for s in score]
        return res

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
class Solution:
	# 希尔排序
    def shellSort(self, arr):
        size = len(arr)
        gap = size // 2
        while gap > 0:
            for i in range(gap, size):
                temp = arr[i]
                j = i
                while j >= gap and arr[j - gap] < temp:
                    arr[j] = arr[j - gap]
                    j -= gap
                arr[j] = temp
            gap = gap // 2
        return arr

    def findRelativeRanks(self, score: List[int]) -> List[str]:
    	#浅复制，保留原数组数据
        nums = score.copy()
        nums = self.shellSort(nums)
        #创建字典保留数值及排序
        score_map = dict()
        for i in range(len(nums)):
            score_map[nums[i]] = i + 1

        res = []
        #重新赋值
        for i in range(len(score)):
            if score[i] == nums[0]:
                res.append("Gold Medal")
            elif score[i] == nums[1]:
                res.append("Silver Medal")
            elif score[i] == nums[2]:
                res.append("Bronze Medal")
            else:
            #否则保留数值排序标号
                res.append(str(score_map[score[i]]))
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        arr = []
        #双指针排序
        index_A, index_B = 0, 0
        while index_A < m and index_B < n:
            if A[index_A] <= B[index_B]:
                arr.append(A[index_A])
                index_A += 1
            else:
                arr.append(B[index_B])
                index_B += 1
        while index_A < m:
            arr.append(A[index_A])
            index_A += 1
        while index_B < n:
            arr.append(B[index_B])
            index_B += 1
        for i in range(m + n):
            A[i] = arr[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1 = m - 1
        p2 = n - 1
        p = m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] = nums1[p1]
                p1 -= 1
            p -= 1

        nums1[:p2+1] = nums2[:p2+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        numDict = dict()
        for num in nums:
            if num in numDict:
                numDict[num] += 1
            else:
                numDict[num] = 1
        max = 0
        max_index = -1
        for num in numDict:
            if numDict[num] > max:
                max = numDict[num]
                max_index = num
        return max_index

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
class Solution:
    def heapify(self, nums: [int], index: int, end: int):
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子节点
            max_index = index
            if nums[left] > nums[max_index]:
                max_index = left
            if right <= end and nums[right] > nums[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换，则说明已经交换结束
                break
            nums[index], nums[max_index] = nums[max_index], nums[index]
            # 继续调整子树
            index = max_index
            left = index * 2 + 1
            right = left + 1

    # 初始化大顶堆
    def buildMaxHeap(self, nums: [int], k: int):
        # (k-2) // 2 是最后一个非叶节点，叶节点不用调整
        for i in range((k - 2) // 2, -1, -1):
            self.heapify(nums, i, k - 1)
        return nums

    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        size = len(arr)
        if k <= 0 or not arr:
            return []
        if size <= k:
            return arr

        self.buildMaxHeap(arr, k)
        for i in range(k, size):
            if arr[i] < arr[0]:
                arr[i], arr[0] = arr[0], arr[i]
                self.heapify(arr, 0, k - 1)

        return arr[:k]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count = [0 for _ in range(1010)]
        for num1 in arr1:
            count[num1] += 1
        res = []
        for num2 in arr2:
            while count[num2] > 0:
                res.append(num2)
                count[num2] -= 1

        for num in range(len(count)):
            while count[num] > 0:
                res.append(num)
                count[num] -= 1

        return res

1
2
3
4
5
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        numDict = dict()
        for i in range(len(nums)):
            num = nums[i]
            if num in numDict:
                return True
            else:
                numDict[num] = num
        return False

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        ans = 0
        for i in range(len(nums)):
            ans ^= nums[i]
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])

        ans = []
        for interval in intervals:
            if not ans or ans[-1][1] < interval[0]:
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import functools

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def cmp(a, b):
            if a + b == b + a:
                return 0
            elif a + b > b + a:
                return 1
            else:
                return -1

        nums_s = list(map(str, nums))
        nums_s.sort(key=functools.cmp_to_key(cmp))
        return ''.join(nums_s)

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
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 调整为大顶堆
        def heapify(nums, index, end):
            left = index * 2 + 1
            right = left + 1
            while left <= end:
                # 当前节点为非叶子节点
                max_index = index
                if nums[left] > nums[max_index]:
                    max_index = left
                if right <= end and nums[right] > nums[max_index]:
                    max_index = right
                if index == max_index:
                    # 如果不用交换，则说明已经交换结束
                    break
                nums[index], nums[max_index] = nums[max_index], nums[index]
                # 继续调整子树
                index = max_index
                left = index * 2 + 1
                right = left + 1
                
        # 初始化大顶堆
        def buildMaxHeap(nums):
            size = len(nums)
            # (size-2) // 2 是最后一个非叶节点，叶节点不用调整
            for i in range((size - 2) // 2, -1, -1):
                heapify(nums, i, size - 1)
            return nums

        buildMaxHeap(nums)
        size = len(nums)
        for i in range(k-1):
            nums[0], nums[size-i-1] = nums[size-i-1], nums[0]
            heapify(nums, 0, size-i-2)
        return nums[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left = 0
        right = len(nums) - 1
        index = 0
        while index <= right:
            if index < left:
                index += 1
            elif nums[index] == 0:
                nums[index], nums[left] = nums[left], nums[index]
                left += 1
            elif nums[index] == 2:
                nums[index], nums[right] = nums[right], nums[index]
                right -= 1
            else:
                index += 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def insertionSort(self, arr):
        for i in range(1, len(arr)):
            temp = arr[i]
            j = i
            while j > 0 and arr[j - 1] > temp:
                arr[j] = arr[j - 1]
                j -= 1
            arr[j] = temp
            
        return arr
    
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.insertionSort(nums)

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
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def randomPartition(nums, low, high):
            i = random.randint(low, high)
            nums[i], nums[high] = nums[high], nums[i]
            return partition(nums, low, high)

        def partition(nums, low, high):
            x = nums[high]
            i = low-1
            for j in range(low, high):
                if nums[j] <= nums[high]:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            nums[i+1], nums[high] = nums[high], nums[i+1]
            return i+1

        def quickSort(nums, low, high, k):
            n = len(nums)
            if low < high:
                pi = randomPartition(nums, low, high)
                if pi == n-k:
                    return nums[len(nums)-k]
                if pi > n-k:
                    quickSort(nums, low, pi-1, k)
                if pi < n-k:
                    quickSort(nums, pi+1, high, k)

            return nums[len(nums)-k]

        return quickSort(nums, 0, len(nums)-1, k)

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
import bisect

class BinaryIndexTree:

    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 1)]

    def lowbit(self, index):
        return index & (-index)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += self.lowbit(index)

    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.lowbit(index)
        return res

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        size = len(nums)
        sort_nums = sorted(nums)
        for i in range(size):
            nums[i] = bisect.bisect_left(sort_nums, nums[i]) + 1

        bit = BinaryIndexTree(size)
        ans = 0
        for i in range(size):
            bit.update(nums[i], 1)
            ans += (i + 1 - bit.query(nums[i]))
        return ans

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
import bisect

class BinaryIndexTree:

    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 1)]

    def lowbit(self, index):
        return index & (-index)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += self.lowbit(index)

    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.lowbit(index)
        return res

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        # 离散化
        sort_nums = list(set(nums))
        sort_nums.sort()
        size_s = len(sort_nums)
        bit = BinaryIndexTree(size_s)

        ans = [0 for _ in range(size)]
        for i in range(size - 1, -1, -1):
            index = bisect.bisect_left(sort_nums, nums[i]) + 1
            ans[i] = bit.query(index - 1)
            bit.update(index, 1)

        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def radixSort(self, arr):
        size = len(str(max(arr)))

        for i in range(size):
            buckets = [[] for _ in range(10)]
            for num in arr:
                buckets[num // (10 ** i) % 10].append(num)
            arr.clear()
            for bucket in buckets:
                for num in bucket:
                    arr.append(num)

        return arr

    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        arr = self.radixSort(nums)
        return max(arr[i] - arr[i-1] for i in range(1, len(arr)))