从排序数组中删除重复项、加一、买股票的最佳时机和移动零

从排序数组中删除重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例1

给定数组 nums = [1,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。
你不需要考虑数组中超出新长度后面的元素。

说明

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
const len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (let i = 0; i < len; i++) {
print(nums[i]);
}

方法一

思路

我们先遍历数组,若发现相同的相邻项,将该元素删除。此时数组的长度也会发生变化,我们需要把 i - 1,保证遍历顺序不会出错。最后,再返回数组的长度。

详解

  1. 遍历数组里的元素;

  2. 判断该元素的相邻项是否与之相同;

  3. 若相同,则删除该元素,同时将数组长度减一,继续遍历;

  4. 待遍历结束时,返回数组的新长度。

代码

const removeDuplicates = function (nums) {
// 遍历数组
for (let i = 1; i < nums.length; i++) {
// 若该元素的相邻项与之相同,则删除该元素
if (nums[i - 1] === nums[i]) {
nums.splice(i - 1, 1);
// 因删除该元素后,数组长度会减一,故 i 也需要减一
i--;
}
};
return nums.length;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    共执行了 n 次,因此时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

    没有申请额外的空间,因此空间复杂度为 O(1)O(1)

方法二

思路

我们用 count 来记录不重复的下标数量,第一个数必定不是重复的,即 nums[0] 肯定是不重复的,所以从第二项(即 nums[1])开始,遍历数组,判断该下标的值跟不重复的数组最后一个元素 nums[count] 是否相同,如果不相同,将该元素值赋值给 nums[count + 1] ,然后 count++,继续遍历。待遍历结束时,我们可以通过 count 数量来判断不重复元素个数,因为 count 是从 0 开始的,故返回的新数组的长度为 count + 1。

比如原数组为 [0,0,1,1,1,2,2,3,4],经过遍历会变成类似 [0,1,2,3,4,x,x,x,x] 的结构,此时 count = 4,返回新数组长度 count + 1 = 5。

详解

  1. 创建字段 count,用来记录不重复的下标数量,初始值为 0;

  2. 因数组的第一个元素(即 nums[count = 0])必定是不重复的,故从数组第二项开始(即 nums[1])开始,遍历数组里的元素;

  3. 判断数组当前元素是否与 nums[count] 相等,若不同,得知当前元素并未重复,将该元素值赋值给 nums[count + 1] ,然后 count++,继续遍历;

  4. 待遍历结束,我们可以通过 count 数量来判断不重复元素个数,因为 count 是从 0 开始计数的,故返回的新数组的长度为 count + 1。

代码

const removeDuplicates = function (nums) {
let count = 0;
// 遍历数组
for (let i = 1; i < nums.length; i++) {
// 若该下标的值跟不重复的数组最后一个元素不相同,则该值添加到不重复数组后一位
if (nums[count] !== nums[i]) {
nums[count + 1] = nums[i];
count++;
}
};
// 因为 count 是从 0 开始的,故返回的数组长度加一
return count + 1;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)

加一

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

方法一 奇技淫巧

思路

我们可以把数组转化成数字加一,然后再转成数组

详解

利用数数的 join 方法,转成数字。

在提交代码时发现有 6145390195186705543 溢出的情况,使用 BigInt 来解决。

加一之后使用 toString方法,转换成字符,最后 split 成数组。

BigIntJavaScript 中的一个新的原始类型,可以用任意精度表示整数。使用 BigInt,即使超出JavaScript Number 的安全整数限制,也可以安全地存储和操作大整数。

代码

/**
* @param {number[]} digits
* @return {number[]}
*/
const plusOne = function (digits) {
return (BigInt(digits.join('')) + 1n).toString().split('');
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    复杂度与输入数组的长度线性相关,为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

    没有申请额外空间,复杂度为 O(1)O(1)

方法二 进位相加

思路

我们可以模拟加法的操作

1 2 3
+ 1
-------
1 2 4

详解

在实际情况中,加一有且只有以下两种情况:

  • 9 加一进位

  • 其他数字加一

先把个位的数加一,如果没有进位就直接推出循环。

如果进位了,再把十位的数加一,个位数设置为0,如此循环,,直到判断没有再进位就退出循环返回结果。

9 9
+ 1
-------
1 0 0

对于 9、99 这种情况,需要进行补位

代码

const plusOne = function (digits) {
for (let i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10; // 9 + 1 = 10 ---> 0 判断有没有进位
if (digits[i] !== 0) {
return digits; // 最后没有进位直接返回
}
}
digits.splice(0, 0, 1);
return digits;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    复杂度与输入数组的长度线性相关,复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

    没有申请额外空间,复杂度为 O(1)O(1)

买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

方法一

思路

定一个滑动窗口,滑动窗口内所有的价格从后向前是递减,如若不是则调整下标,满足该条件。前一个下标从后向前遍历,两个下标初始位置为数组最后一个。如果遇到价格不是递减,则相减得出利润差,并移动两个下标到新的起点。如此遍历直到第一日。

详解

  1. 初始化滑动窗口的两个下标,前下标从后向前遍历。

  2. 如果遇到价格不是递减的情况,则相减得出利润差,并移动两个下标到新的起点。

  3. 如此遍历直到第一日。

代码

const maxProfit = (prices) => {
// 总利润
let num = 0;
// 滑动窗口后一个下标
let aftOff = prices.length - 1;
// 滑动串口前一个下标
let offset = prices.length - 1;
while (offset > 0) {
// 价格递减则移动前一个下标,否则计算出利润差并移动两个下标到新的起点
if (prices[offset] > prices[offset - 1]) {
offset -= 1;
} else {
num += prices[aftOff] - prices[offset];
offset -= 1;
aftOff = offset;
}
}
// 价格递减到第一日情况的逻辑补充
if (aftOff !== offset) {
num += prices[aftOff] - prices[offset];
}
return num;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    假设 nn 为给定数组的长度,while 循环执行了 nn 次,因此,时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1) 该解法中,申请了常数个变量,因此,空间复杂度为 O(1)O(1)

方法二

思路

遍历每日的价格,从第二天起,如果每日的价格都比前一日的价格高,则相减得出利润差,累加在总利润上,直到遍历到最后一日。

详解

  1. 从前向后遍历数组,从第二个开始

  2. 如果当前日的价格比前一日的价格高,则相减得出利润差,累加在总利润上。

  3. 遍历到最后一日,退出循环,返回总利润

代码

const maxProfit = function (prices) {
// 总收益
const totalBenefit = 0;
// 当前日下标
const offset = 1;
const len = prices.length;
while (offset <= len - 1) {
// 如果当日价格比前一天价格高,则相减得出收益
const curPrice = prices[offset];
const prePrice = prices[offset - 1];
if (curPrice > prePrice) {
totalBenefit += curPrice - prePrice;
}
offset += 1;
}
return totalBenefit;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明

  1. 必须在原数组上操作,不能拷贝额外的数组。

  2. 尽量减少操作次数。

注意事项

  1. 由于题目要求必须在原数组上操作,数组的 filter Api 或是 sort 算法,都是不必考虑的。

  2. 切记不要边遍历数组边修改数组长度,如:splice,push,pop等。

方法一 双指针

思路

创建两个指针 ijj 来记录非零元素的下标。遍历遇到一个非零元素时,就把 j 往右挪

遍历结束后,j 指向了最后一个非零元素的下标,再把剩余地址填充 0 即可

详解

  1. i 用于遍历数组,j 来记录非零元素的下标

  2. 当发现 num[i] !== 0 时,说明找到非零元素,把第 ji 指向的两个元素交互位置,再把 j 往右挪

  3. 遍历结束把剩余的地址填充 0

const moveZeroes = function (nums) {
let j = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
nums[j] = nums[i];
j++;
}
}
// 遍历完了,把尾部的元素填充 0 即可
nums.fill(0, j, nums.length);
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    算法包括一次遍历,运行次数与数组长度一致,所以时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

    额外空间包括若干个常量

方法二 双指针优化

思路

方法一进行了两次循环,还能进一步优化,只循环一次。

详解

思路与方法 1 极其相似,依次用非零元素与零元素交换即可,优点在于一步到位,不用再次填充 0。 1. 用 j 记录非零元素的下标,初始为 0 2. 依次用非零元素与 j 对应元素交换位置,每次交换后,j 加 1,j 对应元素就被替换成了 0(除初始值) 3. 零元素不用处理,会被替换或者保持不变。

const moveZeroes = function (nums) {
let j = 0;
let temp = '';
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j++;
}
}
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)