数组
定义
数组（Array）是有限个相同类型的变量组成的有序集合。
特点
- 线性
- 连续的内存空间
- 存储相同类型数据
数组因为有连续的内存空间和相同类型的数据，它才有了一个特性：随机访问。根据下标访问数组的时间复杂度是 O(1)。
但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作，效率可想而知。
低效的插入/删除
插入
假设数组的长度为 n，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第k个位置腾给新数据，我们需要将第k～n这部分的元素顺序性地往后挪一位。这样的插入的时间复杂度是多少？
不难想出，跟位置k的有很大的关系。
- 如果在数组末尾插入元素，那就不需要移动数据了，这时的时间复杂度为O(1)。
- 如果在数组开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是O(n)。
因为我们在每个位置插入元素的概率是一样的，所以平均时间复杂度为(1+2+…n)/n=O(n)。
如果数据有序，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移k之后的数据。 如果数组无序，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第k个位置，为了避免大规模的数据搬移，我们可以直接将第k位的数据搬移到数组元素的最后，把新元素直接放入第k个位置。这种特殊的处理技巧，可以在特定场景下将插入元素的时间复杂度降到 O(1)。（快排中会用到这个处理思想）
删除
和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为O(1)。 如果删除开头的数据，则最坏情况时间复杂度为O(n)；平均情况时间复杂度也为O(n)。
实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？
我们来看一个例子。数组a[10]中存储了8个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除a，b，c三个元素。
为了避免d，e，f，g，h这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
这不就是 JVM 标记清除垃圾回收算法的核心思想吗？
数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。
补充
- 线性表（Linear List）
线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组，链表、队列、栈等也是线性表结构。
- 数组访问越界
数组长度是固定的，越界访问可能会引发异常错误哦。
练习题
加一 [easy]
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
func plusOne(digits []int) []int {
ret := make([]int,1)
btn := 0 // 标记是否进1
l := len(digits)
for i:=l-1; i >=0; i-- {
digits[i]+=btn
btn = 0
if i == l - 1 {
digits[i]++
}
if digits[i] == 10 {
btn = 1
digits[i]=digits[i]-10
}
}
if btn == 1 {
ret[0] = 1
ret = append(ret, digits...)
} else {
ret = digits
}
return ret
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)
删除排序数组中的重复项 [easy]
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
func removeDuplicates(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
slow := 1
for fast := 1; fast < n; fast++ {
if nums[fast] != nums[fast-1] {
nums[slow] = nums[fast]
slow++
}
}
return slow
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)
// 利用 go
func removeDuplicates(nums []int) int {
i := 0
for i + 1 < len(nums) {
if nums[i] == nums[i+1] {
nums = append(nums[:i], nums[i+1:]...)
} else {
i++
}
}
return len(nums)
}
买卖股票的最佳时机 [medium]
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
func maxProfit(prices []int) (int) {
p,l := 0, len(prices)
for i:=1; i < l; i++ {
p += max(0, prices[i] - prices[i-1])
}
return p
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)
旋转数组 [medium]
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
// 翻转数组
func reverse(nums []int) {
i,j := 0, len(nums)-1
for i<j {
nums[i],nums[j] = nums[j],nums[i]
i++
j--
}
}
func rotate(nums []int, k int) {
// 当数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。
k = k%len(nums)
reverse(nums[:len(nums)-k])
reverse(nums[len(nums)-k:])
reverse(nums)
}
// 时间复杂度：O(n)。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。
// 空间复杂度：O(1)。
只出现一次的数字 [easy]
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
func singleNumber(nums []int) int {
single := 0
for _, num := range nums {
single ^= num
}
return single
}
// 时间复杂度：O(n)。
// 空间复杂度：O(1)。
关注和赞赏都是对小欧莫大的支持！ 🤝 🤝 🤝
