一、Leetcode27.移除元素
1.题目描述
给你一个数组 nums和一个值 val，你需要 [原地] 移除所有数值等于 val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 [原地 ]修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
2.暴力破解
public int removeElement(int[] nums, int val) {
int size = nums.length;
for (int i = 0; i < size; i++) {
if (nums[i] == val) {
for (int j = i + 1; j < nums.length; j++) {
nums[j - 1] = nums[j];
}
size--;
i--;
}
}
return size;
}
- size–: 当遇到了数组中和目标相等的元素，说明是要移除的，所以size–
- i–: 因为在遇到了需要移除的元素之后，是用后面的元素覆盖了前面的元素，所以当进入了if判断之后，说明后面一个待比较的新的元素已经移动到前一位去了，所以i–，才可以再比较到这个移动到了前面的新的元素。
3.双指针
public static int removeElementDoublePoint(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
定义一个快指针fast，用来正常的遍历元素；
定义一个慢指针slow，用来指向新的数组的元素（删除了目标元素后的）
没有遇到目标元素时所指向的元素（符合的元素），都存入新数组（slow指向）
二、Leetcode977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
1.暴力破解
遍历数组的每一个元素，算出平方。再对结果进行排序
public static int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] = nums[i] * nums[i];
}
return insertSort(nums);
}
/**
* 选择排序
*
* @param nums
* @return
*/
private static int[] selectSort(int[] nums) {
for (int j = 0; j < nums.length; j++) {
int minValueIndex = j;
for (int k = j + 1; k < nums.length; k++) {
// 找出索引最小的
minValueIndex = nums[k] < nums[minValueIndex] ? k : minValueIndex;
}
//把找到的下标和第j个元素交换 nums[j] nums[minValueIndex]
int temp = nums[j];
nums[j] = nums[minValueIndex];
nums[minValueIndex] = temp;
}
return nums;
}
/**
* 插入排序
*
* @param nums
* @return
*/
private static int[] insertSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i; j > 0; j--) {
if (nums[j] < nums[j - 1]) {
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
} else {
break;
}
}
}
return nums;
}
2.双指针
头指针和尾指针，头指针从下标0开始，尾指针从最后一个元素（下标nums.length-1）开始，头指针前进，尾指针后退，直到相遇就是遍历完了；遍历的过程中，每次都取出更大的那个数，存入一个新的数组中，从最后一个下标往前存，因为是非递减的。
public static int[] sortedSquares(int[] nums) {
int start = 0;
int end = nums.length - 1;
int[] sortedSquareNums = new int[nums.length];
int index = nums.length - 1;
while (start <= end) {
int startSquare = nums[start] * nums[start];
int endSquare = nums[end] * nums[end];
if (startSquare > endSquare) {
sortedSquareNums[index] = startSquare;
start++;
} else {
sortedSquareNums[index] = endSquare;
end--;
}
index--;
}
return sortedSquareNums;
}
前提是数组是非递减的，如果是乱序的，此方案行不通
