算法day01_ 27. 移除元素、977.有序数组的平方

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;}
}