Go数组及相关算法（上）

date
tag , ,

对 Go 数组和相关算法进行了学习，并做了笔记。
相关链接：代码随想录

# Go 数组

# 定义相关

数组是存放在连续内存空间上的相同类型数据的集合。

数组是具有相同类型的一组已编号且长度固定的数据项序列。这种类型可以是任意的原始类型（int、string或者自定义类型）。

数组元素可以通过索引来读取或修改。

img

数组定义： var a [len]int，例如 var a [5]int

数组的大小len必须是常量，且是类型的组成部分（数组的类型不仅由 元素类型 决定，还由 长度 决定，例如[5]int 和 [10]int 是 两种完全不同的类型）。

数组大小一旦定义后不可变。

内置函数 len 和 cap 都会返回数组大小

需要注意：

  • 数组的下标都是从0开始的
  • 数组内存空间的地址是连续的

正是因为数组在内存空间的地址是连续的，所以在“删除”元素时需要移动其他元素的地址。数组的元素不能删，只能覆盖。

算法通关数组1

遍历数组：

for i := 0; i < len(a); i++ {
    //...
}
for index, v := range a {
    //...
}

访问越界，如果下标在数组合法范围之外，则触发访问越界，会panic

数组是值类型，赋值和传参会复制整个数组，而不是指针。因此改变副本的值，不会改变本身的值。

值拷贝会出现性能问题，通常会使用 slice 或数组指针。

Go 数组支持 “==”、”!=” 操作符，因为数组是值类型，内存总是被初始化为对应类型的0值。

指针数组 [n]*T，数组指针 *[n]T 。

# 数组的初始化

// 全局:
var numbers [5]int //初始值为0
var arr0[5]int = [5]int{1, 2, 3}
var arr1 = [5]int{1, 2, 3, 4, 5}	// 使用初始化列表来初始化数组的元素
var arr2 = [...]int{1, 2, 3, 4, 5, 6}	// 数组长度不确定，使用...代替数组长度，编译器会根据元素个数自行推断数组长度
var str = [5]string{3: "hello world", 4: "kira"}	// 如果设置了数组长度，可以通过指定下标来初始化元素

// 局部:
a := [3]int{1, 2}	// 未初始化的元素值为0
b := [...]int{1, 2, 3, 4}	// 通过初始化值来确定数组长度
c := [5]int{2:100, 4:200}	// 使用下标来初始化元素
d := [...]struct {
    name string
    age string
    // 这里是数组元素类型struct
}{
    {"user1", 10},
    {"user2", 20},	// 2个元素
}

# Go 向函数中传递数组

Go 语言中的数组是值类型，因此将数组传递给函数时，实际上传递的是数组的副本。

向函数传递数组参数，需要在函数定义时声明形参为数组。

func aFunc(arr [10]int) {
    ...
}
// 或者
func bFunc(arr []int) {
    ...
}

如果想要在函数内修改原始数组，需要传递数组的指针

package main

import "fmt"

// 函数接受一个数组作为参数
func modifyArray(arr [5]int) {
    for i := 0; i < len(arr); i++ {
        arr[i] = arr[i] * 2
    }
}

// 函数接受一个数组的指针作为参数
func modifyArrayWithPointer(arr *[5]int) {
    for i := 0; i < len(*arr); i++ {
        (*arr)[i] = (*arr)[i] * 2
    }
}

func main() {
    // 创建一个包含5个元素的整数数组
    myArray := [5]int{1, 2, 3, 4, 5}

    fmt.Println("Original Array:", myArray)

    // 传递数组给函数，但不会修改原始数组的值
    modifyArray(myArray)
    fmt.Println("Array after modifyArray:", myArray)

    // 传递数组的指针给函数，可以修改原始数组的值
    modifyArrayWithPointer(&myArray)
    fmt.Println("Array after modifyArrayWithPointer:", myArray)
}

输出结果

Original Array: [1 2 3 4 5]
Array after modifyArray: [1 2 3 4 5]
Array after modifyArrayWithPointer: [2 4 6 8 10]

# 多维数组

img

一个二维数组 a 为三行四列，二维数组中的元素可通过 a[ i ][ j ] 来访问。

// 全局
var arr0 [5][3]int
var arr1 [2][3]int = [...][3]int{{1, 2, 3}, {7, 8, 9}}
// 局部
a := [3][4]int{  
    {0, 1, 2, 3} ,   /*  第一行索引为 0 */
    {4, 5, 6, 7} ,   /*  第二行索引为 1 */
    {8, 9, 10, 11},   /* 第三行索引为 2 */
}
b := [...][2]int{{1, 1}, {2, 2}, {3, 3}} // 第 2 纬度不能用 "..."。

多维数组遍历

package main

import (
    "fmt"
)

func main() {

    var f [2][3]int = [...][3]int{{1, 2, 3}, {7, 8, 9}}

    for k1, v1 := range f {
        for k2, v2 := range v1 {
            fmt.Printf("(%d,%d)=%d ", k1, k2, v2)
        }
        fmt.Println()
    }
}

输出结果

(0,0)=1 (0,1)=2 (0,2)=3 
(1,0)=7 (1,1)=8 (1,2)=9

# 704.二分查找

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

使用二分查找的前提：有序数组；无重复元素。

边界处理是重要问题。

主流写法有2类，左闭右闭[left, right]和左闭右开[left, right)。

# 左闭右闭区间[left, right]

x >> n相当于除以 2^n 并向下取整。

mid := left + (right-left)>>1是常见的二分中点写法，直接相加除以二可能会导致数值溢出。

left := 0

right := len(num) - 1

*判断 left < right 时有没有=，需要看区间[left, right]。

左闭右闭，left == right 在这个区间内有意义，所以需要 <=

*更新区间边界，以下是伪代码

if num[mid] == target

​ return mid

else if num[mid] > target

​ 更新右边界，如下图所示。因为区间[left, right]右闭包含 right，并且上面的判断条件 mid ！= target，所以

​ right = mid - 1 。

else // num[mid] < target

​ 更新左边界，左闭包含 left，left != target， 所以

​ left = mid + 1

704.二分查找

func search(nums []int, target int) int {
    // 左闭右闭 [left, right]
    // 初始化左右边界
    left := 0
    right := len(nums) - 1

    for left <= right {
        mid := left + (right - left) >> 1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            // 更新左边界，mid 不是 target，所以left应该为 mid+1
            left = mid + 1
        } else {
            // 更新右边界， mid > targer,所以right 应该为 mid-1 
            right = mid - 1
        }
    }
    return -1
}

# 左闭右开区间[left, right)

left := 0

right := len(num)

由于右开， right 应当是数组元素综述+1才不会漏元素

*条件判断时，left < right ，因为 left == right 在区间[left, right)中没有意义。

*更新区间边界

if num[mid] == target

​ return mid

else if num[mid] > target

​ 更新右边界。num[mid] != target，又因为右开，所以

​ right = mid

else // num[mid] < target

​ 更新左边界， 因为左闭，应当包含边界，而 num[mid] != target 所以

​ left = mid + 1

func search(nums []int, target int) int {
    // 左闭右开 [left, right)
    // 初始化左右边界
    left := 0
    right := len(nums)

    for left < right {
        mid := left + (right - left) >> 1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            // 更新左边界，mid 不是 target，所以left应该为 mid+1
            left = mid + 1
        } else {
            // 更新右边界， mid > targer,所以right 应该为 mid-1 
            right = mid
        }
    }
    return -1
}

遗留：什么是循环不变量？

# 27. 移除元素

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

>int[] nums = [...]; // 输入数组
>int val = ...; // 要移除的值
>int[] expectedNums = [...]; // 长度正确的预期答案。
                           // 它以不等于 val 的值排序。

>int k = removeElement(nums, val); // 调用你的实现

>assert k == expectedNums.length;
>sort(nums, 0, k); // 排序 nums 的前 k 个元素
>for (int i = 0; i < actualLength; i++) {
   assert nums[i] == expectedNums[i];
>}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

>输入：nums = [3,2,2,3], val = 3
>输出：2, nums = [2,2,_,_]
>解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
>你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

>输入：nums = [0,1,2,2,3,0,4,2], val = 2
>输出：5, nums = [0,1,4,0,3,_,_,_]
>解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
>注意这五个元素可以任意顺序返回。
>你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

# 暴力解法

时间复杂度是O(n^2)

两层 for 循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

一旦第一层 for 循环找到 val ，就用其后面的元素把它往前一位覆盖掉，并且数组大小 len-1

27.移除元素-暴力解法

func removeElement(nums []int, val int) int {
    len := len(nums)
    for i := 0; i < len; i++ {
        if nums[i] == val {
            for j := i + 1; j < len; j++ {
                nums[j-1] = nums[j]
            }
            i--
            len--
        }
    }
    return len
}

# 快慢指针法

时间复杂度：O(n)；空间复杂度：O(1)

没有改变元素的相对位置

  • 快指针：寻找新数组元素（非val的元素）
  • 慢指针：指向要更新的元素，新数组的下标。

快指针一旦找到新数组元素，就更新慢指针的元素，直到找完就得到了全部是非 val 元素的新数组。

slowIndex 刚好就是新数组大小。

27.移除元素-双指针法

func removeElement(nums []int, val int) int {
    var slowIndex int = 0
    len := len(nums)
    for fastIndex := 0; fastIndex < len ; fastIndex++ {
        if nums[fastIndex] != val {
            nums[slowIndex] = nums[fastIndex]
            slowIndex++
        }
    }
    return slowIndex
}

# 双向指针法

有点像二分查找，这里按照左闭右闭来写。

双向指针法，left找 val，right找非 val，一旦都找到，就 nums[left] = nums[right]
随后 left++ ; right– (都向中间靠拢)
当 left > right 时，说明left左侧没有 val，left 指针左侧即是最终的数组，left 就是数组大小。

过程：

func removeElement(nums []int, val int) int {
    left := 0
    right := len(nums) - 1
    // 左闭右闭区间，所以是 <=
    for left <= right {
        // 寻找左侧val，找到退出循环
        for left <= right && nums[left] != val {
            left++
        }
        // 寻找右侧非val，找到退出循环
        for left <= right && nums[right] == val {
            right--
        }
        // 各自都找到后开始覆盖
        if left < right {
            nums[left] = nums[right]
            left++
            right--
        }
    }
    return left
}

# 977.有序数组的平方

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

# 暴力解法 直接平方排序

O(n + nlogn) 或是 O(nlogn)

func sortedSquares(nums []int) []int {
    for i, val := range(nums) {
        nums[i] *= val 
    }
    sort.Ints(nums)
    return nums
}

# 双指针法

O(n)

数组是有序的，平方之后的数组，最大的数分别在两端，越往中间越小。

创建新数组 ans，以及k（数组的最大下标）。

两端的下标 left, right（左闭右闭）。nums[left]^2 和 nums[right]^2 做比较。

大的填入 ans[k]，然后大的指针–，k–，另一个不动留着下一次比较。即：

如果A[i] * A[i] < A[j] * A[j] 那么ans[k--] = A[j] * A[j]; j--。

如果A[i] * A[i] >= A[j] * A[j] 那么ans[k--] = A[i] * A[i]; i++。

下图在最后应该是 i 和 j 相等，都到元素0再判断平方大小，动画可能少了一张图。

img

func sortedSquares(nums []int) []int {
    len := len(nums)
    var left, right, k int = 0, len-1, len-1
    ans := make([]int, len)
    for left <= right {
        lsq, rsq := nums[left]*nums[left], nums[right]*nums[right]
        if lsq > rsq {
            left++
            ans[k] = lsq
            k--
        } else {
            right--
            ans[k] = rsq
            k--
        }
    }
    return ans
}
归档 友链
arrow_up
theme