吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

算法基础 - 数组

Posted at 2021-03-18Updated at 2021-04-28 算法  算法 数据结构 leetcode 

数组是最基础的数据结构之一，存储线性数据，内存结构连续。

数组是Go的内置类型，分为静态数组和动态切片。

1
2
3
4
5
6
7
8
9
10
11
12
var array [3]int
var slice []int

// Append
array = append(array, 1)
// Prepend
array = append([]int{1}, array...)

type struct Node {
    Value int
    Next  *Node
}

# 实践

# 多个有序数组的第k小数

寻找两个正序数组的中位数

  • 暴力法: 归并排序后取中位数
  • 指针法：只计中位数
  • 通用寻找第k小数方法
    • 二分法比较排除较小数组的前k/2个元素
    • 递归查找(k - k/2)/2个元素

# 二分法-升序数组搜索插入位置

搜索插入位置

  • 暴力法，直接搜索，时间复杂度O(n)
1
2
3
4
5
6
7
8
func searchInsert(nums []int, target int) int {
    for i, n := range nums {
        if n >= target {
            return i
        }
    }
    return len(nums)
}
  • 二分法，时间复杂度O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    for left <= right {
        middle := (right + left) / 2
        if nums[middle] > target {
            right = middle - 1
        } else if nums[middle] < target {
            left = middle + 1
        } else {
            return middle
        }
    }
    return right + 1
}

# 双指针法-数组原地移除元素

移除元素

  • 暴力法，查到一个挪一个，时间复杂度O(n2)，空间复杂度O(1)
  • 快慢指针法，时间复杂度O(n)，空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

# 滑动窗口-长度最小的连续子数组

长度最小的子数组

  • 暴力法，两层循环，记下最小长度，时间复杂度O(n2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func minSubArrayLen(target int, nums []int) int {
    min := len(nums) + 1
    for i := 0; i < len(nums); i++ {
        sum := 0
        for j := 0; j < len(nums) - i; j++ {
            sum += nums[i + j]
            if sum >= target && min > j + 1 {
                    min = j + 1
                    break
            }
        }
    }
    if min == len(nums) + 1 {
        return 0
    }
    return min
}
  • 滑动窗口，右指针不断右移，当不满足条件时，左指针右移直到满足条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func minSubArrayLen(target int, nums []int) int {
    l := 0
    sum, min := 0, len(nums) + 1
    for r := 0; r < len(nums); r++ {
        sum += nums[r]
        for sum >= target {
            if min > r - l + 1 {
                min = r - l + 1
            }
            sum -= nums[l]
            l++
        }
    }
    if min == len(nums) + 1 {
        return 0
    }
    return min
}

# 过程模拟-螺旋矩阵

螺旋矩阵II

  • 直接过程模拟，可用递归或迭代方式模拟每圈
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
func drawCircle(n int, x int, y int, length int, count int, m [][]int) {
    if length < 0 {
        return
    }
    if length == 0 {
        count++
        m[y][x] = count
        return
    }

    for i := 0; i < length; i++ {
        count++
        m[y][x + i] = count
    }

    for i := 0; i < length; i++ {
        count++
        m[y + i][x + length] = count
    }

    for i := length; i > 0; i-- {
        count++
        m[y + length][x + i] = count
    }

    for i := length; i > 0; i-- {
        count++
        m[y + i][x] = count
    }

    drawCircle(n, x + 1, y + 1, length - 2, count, m)
}

func generateMatrix(n int) [][]int {
    m := make([][]int, n)
    for i := 0; i < n; i++ {
        m[i] = make([]int, n)
    }

    drawCircle(n, 0, 0, n - 1, 0, m)
    return m
}

# 双指针法-平方数之和

平方数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func judgeSquareSum(c int) bool {
    left, right := 0, int(math.Sqrt(float64(c)))
    for left <= right {
        sum := left*left + right*right
        if sum == c {
            return true
        } else if sum > c {
            right--
        } else {
            left++
        }
    }
    return false
}

# 二分法-搜索旋转排序数组

搜索旋转排序数组

Share 

 Previous post: 算法基础 - 哈希表 Next post: 算法基础 - 树 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo