算法刷题笔记 (19) 移动零 调整数组顺序使奇数位于偶数前面 手撕归并排序 最小的k个数

移动零

移动零

解题思路

1. 利用冒泡，元素交换的基本思想：当num[i] == 0 && nums[i+1] != 0时交换元素。若本轮没有交换元素，可以提前跳出循环

2. 双指针法，两次遍历。创建两个指针i和j，第一次遍历的时候指针j记录有多少个非零元素。第一次遍历完后，j指针的下标就指向了最后一个非零元素下标。第二次遍历的时候，起始位置就从j开始，将剩下的这段区域内的元素全部置为0

3. 双指针法，一次遍历。参照了快速排序的基本思想，把0作为中间点，把不等于0的放到中间点的左边，等于0的放到其右边。使用两个指针i和j，只要nums[i]!=0，就交换nums[i]和nums[j]

解题代码

1. 冒泡，元素交换

func moveZeroes(nums []int)  {
    for i := len(nums)-1; i > 0 ; i-- {
        var flag bool   // 标记本轮是否交换过元素
        for j := 0; j < i; j++ {
            if nums[j] == 0 && nums[j+1] != 0 {
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = true
            }
        }
        if !flag {  // 本轮没有发生交换，直接退出循环
            break
        }
    }
}

2. 双指针，两次遍历：

func moveZeroes(nums []int)  {
    i, j := 0, 0    // 双指针
    // 第一遍遍历
    for ; i < len(nums); i++ {
        if nums[i]!= 0 {
            nums[j] = nums[i]
            j++
        }
    }
    // 第二遍遍历
    for ; j < len(nums); j++ {
        nums[j] = 0
    }
}

3. 双指针，一次遍历：

func moveZeroes(nums []int)  {
    i, j := 0, 0
    // 一次遍历
    for ; i < len(nums); i++ {
        if nums[i] != 0 {
            nums[i], nums[j] = nums[j], nums[i]
            j++
        }
    }
}

调整数组顺序使奇数位于偶数前面

调整数组顺序使奇数位于偶数前面

解题思路

基于快速排序的基本思想，奇数在中间点的左边，偶数在中间点的右边

解题代码

func exchange(nums []int) []int {
    low, high := 0, len(nums)-1
    for low < high {
        for low < high && nums[high]%2 == 0 {
            high--
        }
        for low < high && nums[low]%2 == 1 {
            low++
        }
        // 交换nums[low]、nums[high]
        nums[low], nums[high] = nums[high], nums[low]
    }

    return nums
}

手撕归并排序

手撕归并排序

解题思路

归并排序

解题代码

var aux []int   // 用于实现归并的辅助数组

func sortArray(nums []int) []int {
    aux = make([]int, len(nums))
    mergeSort(nums, 0, len(nums))
    return nums
}

func mergeSort(nums []int, low, high int) {     // 归并排序
    if low < high-1 {
        mid := (low+high) / 2
        mergeSort(nums, low, mid)
        mergeSort(nums, mid, high)
        merge(nums, low, mid, high)
    }
}

func merge(nums []int, low, mid, high int) {
    // 将nums[low]~nums[high-1]复制到辅助数组中
    for i := low; i < high; i++ {
        aux[i] = nums[i]
    }
    // 开始归并
    i, j, k := low, mid, low    // i指向辅助数组中第一段有序序列，j指向辅助数组中第二段有序序列，k指向当前合并的位置
    for i < mid && j < high {
        // 每次选择较小者进行合并
        if aux[i] < aux[j] {
            nums[k] = aux[i]
            i++
            k++
        } else {
            nums[k] = aux[j]
            j++
            k++
        }
    }
    // 将剩余元素直接复制
    for i < mid {
        nums[k] = aux[i]
        i++
        k++
    }
    for j < high {
        nums[k] = aux[j]
        j++
        k++
    }
}

最小的k个数

最小的k个数

解题思路

利用堆排序，在建成小根堆后，每一次调整都会选择出堆中最小的元素。所以，对堆进行k次调整，即可得到最小的k个数。

解题代码

func getLeastNumbers(arr []int, k int) []int {
    len := len(arr)
    res := make([]int, k)
    // 建小根堆
    buildHeap(arr, len)
    // 求最小的k个数字
    for k > 0 {
        res[k-1] = arr[0]
        // 堆顶与堆底交换
        arr[0], arr[len-1] = arr[len-1], arr[0]
        len--
        k--
        // 重新调整成小根堆
        adjestHeap(arr, 0, len)
    }

    return res
}

func buildHeap(arr []int, len int) {        // 建堆
    for i := len/2 -1; i >= 0; i-- {    // 从最后一个分支节点开始，向上调整
        adjestHeap(arr, i, len)
    }
}

func adjestHeap(arr []int, i, len int) {    // 以arr[i]为根调整成小根堆
    for 2*(i+1) <= len {
        left := 2*(i+1)-1   //左子树下标
        right := left+1     // 右子树下标
        var smaller int      // 左、右之中较小者的下标
        if right < len && arr[left] > arr[right] {
            smaller = right
        } else {
            smaller = left
        }
        if arr[i] > arr[smaller] {
            arr[i], arr[smaller] = arr[smaller], arr[i]
        }
        i = smaller
    }
}