Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (2) 数组中的第K大元素 K个一组翻转链表 手撕快速排序

发表于 更新于 分类于

数组中的第K大元素

数组中的第K个最大元素

解题思路

  1. 利用快速排序的思想，对数组进行划分。则一趟划分完成后有以下情况：
    • 若枢轴最终就是第K大的元素，则直接返回
    • 若枢轴大于第K大的元素，则对枢轴元素左侧的部分进行划分
    • 若枢轴小于第K大的元素，则对枢轴元素右侧的部分进行划分

解题代码

  1. 基于快速排序
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
func findKthLargest(nums []int, k int) int {
    len := len(nums)    // 数组长度
    low, high, low0, high0 := 0, len-1, 0, len-1
    var pivot int   // 枢轴
    
    for {
        
        pivot = nums[low]   // nums[low]为数轴
        for low < high {    // 对nums[low]~nums[high]以pivot进行划分
            for low < high && pivot <= nums[high] {
                high--
            }
            nums[low] = nums[high]
            for low < high && nums[low] <= pivot {
                low++
            }
            nums[high] = nums[low] 
        }
        nums[low] = pivot   // 枢轴元素最终的下标为low
        
        if low == len-k { // 枢轴刚好是第k大的元素，退出循环
            break
        } else if low < len-k {   // 第k大的元素在枢轴右边，对右边继续划分
            low0 = low + 1
            low = low0
            high = high0
        } else {  // low > len-k    //第k大的元素在枢轴左边，对左边继续划分
            high0 = low - 1
            low = low0
            high = high0
        }
    }

    return nums[low]
}

K个一组翻转链表

K个一组翻转链表

解题思路

  1. 不实际交换节点的位置，而是只改变节点内部的值。因为每K个节点需要逆序写入数据，所以利用一个栈记录这K个节点中的数据。每K个节点中的数据依次压栈，再依次弹出写入到这K个节点中。可以利用指针指向该组的第一个的节点，防止指针回溯，提高时间性能。该方法时间复杂度为O(k)

解题代码

  1. 只修改节点内部的值，不实际交换节点位置
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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    stack, top := make([]int, k), -1 // 定义栈，及其初始化
    var first *ListNode // 记录当前组的第一个节点
    p := head   // 遍历链表的指针
    count := 1
    for p != nil || count == k+1 {  // 当p不为空，或者刚好遍历完一组时进行循环
        if count <= k {
            if count == 1 { // 记录改组的第一个节点
                first = p
            }
            // 节点数据入栈
            top++
            stack[top] = p.Val
            count++
            p = p.Next  // p指针后移
        } else {    // 已经遍历了一组节点（K个）
            for i:= 1; i <= k; i++ {
                // 节点数据依次出栈重新修改这一组节点的数据
                first.Val = stack[top]
                top--
                first = first.Next  // 后移，修改下一个节点的数据
            }
            count = 1 // 计数变量置1
        }
    }

    return head
}

手撕快速排序

手撕快速排序

解题思路

  1. 手撕快速排序

解题代码

  1. 快速排序
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
func sortArray(nums []int) []int {
    QuickSort(nums, 0, len(nums)-1)	// 进行快速排序

    return nums
}

func QuickSort(nums []int, low int, high int){
    if low < high {
        partition := Partition(nums, low, high)	// 以nums[low]为枢轴，进行划分
        QuickSort(nums, low, partition-1)	// 对枢轴左边继续划分
        QuickSort(nums, partition+1, high)	// 对枢轴右边继续划分
    }
}

func Partition(nums []int, low int, high int) int {
    pivot := nums[low]
    for low < high {
        for low < high && pivot <= nums[high] {
            high--
        }
        nums[low] = nums[high]
        for low < high && nums[low] <= pivot {
            low++
        }
        nums[high] = nums[low]
    }
    nums[low] = pivot

    return low
}
  1. 随机选取枢轴的快速排序
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
func sortArray(nums []int) []int {
    QuickSort(nums, 0, len(nums)-1)	// 进行快速排序

    return nums
}

func QuickSort(nums []int, low int, high int){
    if low < high {
        partition := RandomPartition(nums, low, high)	// 随机选取枢轴，进行划分
        QuickSort(nums, low, partition-1)	// 对枢轴左边继续划分
        QuickSort(nums, partition+1, high)	// 对枢轴右边继续划分
    }
}

func RandomPartition(nums []int, low int, high int) int {
    randomIndex := low + rand.Intn(high-low+1)	// 随机选取枢轴
    nums[randomIndex], nums[low] = nums[low], nums[randomIndex]	// 交换
    return Partition(nums, low, high)
}

func Partition(nums []int, low int, high int) int {
    pivot := nums[low]
    for low < high {
        for low < high && pivot <= nums[high] {
            high--
        }
        nums[low] = nums[high]
        for low < high && nums[low] <= pivot {
            low++
        }
        nums[high] = nums[low]
    }
    nums[low] = pivot

    return low
}