27.移除元素
题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
思路
暴力解法主要是两层for循环，一层for循环找到val，一层for循环用于覆盖val，将val后的所有的数组元素全部前移。
双指针法主要是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
- 快指针用于寻找新数组元素的值
- 慢指针用于来确定新数组元素的下标
解法
暴力解法
代码实现
class Solution { public int removeElement(int[] nums, int val) { int length=nums.length; for(int i=0; i<length;i++){ if(nums[i]==val){ for(int j=i+1;j<length;j++){ nums[j-1]=nums[j]; } i--; length--; } } return length; } }
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
快慢指针解法
代码实现
class Solution { public int removeElement(int[] nums, int val) { int slowIndex=0; for(int fastIndex=0;fastIndex<nums.length;fastIndex++){ if(nums[fastIndex]!=val){ nums[slowIndex]=nums[fastIndex]; slowIndex++; } } return slowIndex; } }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
977.有序数组的平方
题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
思路
该题目中给的序列为非递减序列，即有可重复值的递增序列。
暴力解法、快慢指针法都是先平方后排序。
双指针法，使用start下标和end下标进行指向，并将元素平方后的大小判断的结果填入新的数组，在新数组中，从后往前依次填入数组元素。
- 若 nums[startIndex]*nums[startIndex]<nums[endIndex]*nums[endIndex]，那么result[k--]=nums[endIndex]*nums[endIndex];
- 若nums[startIndex]*nums[startIndex]>nums[endIndex]*nums[endIndex]，那么 result[k--]=nums[startIndex]*nums[startIndex];
解法
暴力解法
代码示例：
class Solution { public int[] sortedSquares(int[] nums) { int[] newNums=new int[nums.length]; for(int i=0;i<nums.length;i++){ newNums[i]=nums[i]*nums[i]; } Arrays.sort(newNums); return newNums; } }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
快慢指针法
代码示例：
class Solution { public int[] sortedSquares(int[] nums) { int fastIndex=0; int slowIndex=0; for(fastIndex=0;fastIndex<nums.length;fastIndex++){ nums[slowIndex]=nums[fastIndex]*nums[fastIndex]; slowIndex++; } Arrays.sort(nums); return nums; } }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
双指针法
代码示例
class Solution { public int[] sortedSquares(int[] nums) { int[] result=new int[nums.length]; int k=nums.length-1; int startIndex=0; int endIndex=nums.length-1; while(startIndex<=endIndex){ if(nums[startIndex]*nums[startIndex]<nums[endIndex]*nums[endIndex]){ result[k--]=nums[endIndex]*nums[endIndex]; endIndex--; }else{ result[k--]=nums[startIndex]*nums[startIndex]; startIndex++; } } return result; } }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
