给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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,保证遍历顺序不会出错。最后,再返回数组的长度。
详解
遍历数组里的元素;
判断该元素的相邻项是否与之相同;
若相同,则删除该元素,同时将数组长度减一,继续遍历;
待遍历结束时,返回数组的新长度。
代码
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;};
复杂度分析
时间复杂度:
共执行了 n 次,因此时间复杂度为 。
空间复杂度:
没有申请额外的空间,因此空间复杂度为 。
思路
我们用 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。
详解
创建字段 count,用来记录不重复的下标数量,初始值为 0;
因数组的第一个元素(即 nums[count = 0])必定是不重复的,故从数组第二项开始(即 nums[1])开始,遍历数组里的元素;
判断数组当前元素是否与 nums[count] 相等,若不同,得知当前元素并未重复,将该元素值赋值给 nums[count + 1] ,然后 count++,继续遍历;
待遍历结束,我们可以通过 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;};
时间复杂度:
空间复杂度:
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例
输入: [1,2,3]输出: [1,2,4]解释: 输入数组表示数字 123。
思路
我们可以把数组转化成数字加一,然后再转成数组
详解
利用数数的 join
方法,转成数字。
在提交代码时发现有 6145390195186705543
溢出的情况,使用 BigInt
来解决。
加一之后使用 toString
方法,转换成字符,最后 split
成数组。
BigInt
是 JavaScript
中的一个新的原始类型,可以用任意精度表示整数。使用 BigInt
,即使超出JavaScript Number 的安全整数限制,也可以安全地存储和操作大整数。
代码
/*** @param {number[]} digits* @return {number[]}*/const plusOne = function (digits) {return (BigInt(digits.join('')) + 1n).toString().split('');};
复杂度分析
时间复杂度:
复杂度与输入数组的长度线性相关,为
空间复杂度:
没有申请额外空间,复杂度为
思路
我们可以模拟加法的操作
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;};
复杂度分析
时间复杂度:
复杂度与输入数组的长度线性相关,复杂度为
空间复杂度:
没有申请额外空间,复杂度为
给定一个数组,它的第 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。
思路
定一个滑动窗口,滑动窗口内所有的价格从后向前是递减,如若不是则调整下标,满足该条件。前一个下标从后向前遍历,两个下标初始位置为数组最后一个。如果遇到价格不是递减,则相减得出利润差,并移动两个下标到新的起点。如此遍历直到第一日。
详解
初始化滑动窗口的两个下标,前下标从后向前遍历。
如果遇到价格不是递减的情况,则相减得出利润差,并移动两个下标到新的起点。
如此遍历直到第一日。
代码
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;};
复杂度分析
时间复杂度:
假设 为给定数组的长度,while 循环执行了 次,因此,时间复杂度为 。
空间复杂度: 该解法中,申请了常数个变量,因此,空间复杂度为 。
思路
遍历每日的价格,从第二天起,如果每日的价格都比前一日的价格高,则相减得出利润差,累加在总利润上,直到遍历到最后一日。
详解
从前向后遍历数组,从第二个开始
如果当前日的价格比前一日的价格高,则相减得出利润差,累加在总利润上。
遍历到最后一日,退出循环,返回总利润
代码
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;};
复杂度分析
时间复杂度:
空间复杂度:
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例
输入: [0,1,0,3,12]输出: [1,3,12,0,0]
说明
必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。
注意事项
由于题目要求必须在原数组上操作,数组的 filter Api 或是 sort 算法,都是不必考虑的。
切记不要边遍历数组边修改数组长度,如:splice,push,pop等。
思路
创建两个指针 i
和 j
,j
来记录非零元素的下标。遍历遇到一个非零元素时,就把 j
往右挪
遍历结束后,j
指向了最后一个非零元素的下标,再把剩余地址填充 0 即可
详解
i
用于遍历数组,j
来记录非零元素的下标
当发现 num[i] !== 0
时,说明找到非零元素,把第 j
和 i
指向的两个元素交互位置,再把 j
往右挪
遍历结束把剩余的地址填充 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);};
时间复杂度:
算法包括一次遍历,运行次数与数组长度一致,所以时间复杂度为
空间复杂度:
额外空间包括若干个常量
思路
方法一进行了两次循环,还能进一步优化,只循环一次。
详解
思路与方法 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++;}}};
时间复杂度:
空间复杂度: