|
目录
283.移动零
方法一 双指针法
方法二 一遍遍历
方法三 增强for循环
977.有序数组的平方
方法一：冒泡排序法的思想
方法二：从两边开始比较
方法三：从中间开始比较
283.移动零
题目链接
给定一个数组?nums，编写一个函数将所有?0?移动到数组的末尾，同时保持非零元素的相对顺序。
请注意?，必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
方法一 双指针法
第一段代码是在循环里就把末尾的0替换掉了。
第二段代码又单独设了个count用来记不等于0的个数，循环结束之后为数组末尾添加0。
class Solution {
public void moveZeroes(int[] nums) {
int Slow = 0;
for(int fast = 0; fast < nums.length; fast++) {
if(nums[Slow] != 0) {
Slow++;
}else if(nums[Slow] == 0 && nums[fast] != 0) {
nums[Slow++] = nums[fast];
nums[fast] = 0;
}
}
}
}
class Solution {
public void moveZeroes(int[] nums) {
int fast = 0;
int count = 0;
for(int slow = 0; fast < nums.length; fast++){
if(nums[fast] != 0) {
count++;
nums[slow++] = nums[fast];
}
}
while(count < nums.length){
nums[count++] = 0;
}
}
}
方法二 一遍遍历
只设一个指针来遍历数组，count来记0的个数，count != 0说明数组里面找到了0，如果之后指向的元素不等于0，就让它往前移coun个单位，让当前指向的元素等于0。
class Solution {
public void moveZeroes(int[] nums) {
int count = 0;
for(int point = 0; point < nums.length; point++) {
if(nums[point] == 0) {
count++;
}
if(nums[point] != 0 && count != 0){
nums[point-count] = nums[point];
nums[point] = 0;
}
}
}
}
方法三 增强for循环
增强for循环：遍历nums数组，把值赋给num，注意num不是数组是值，所以在循环里面可以判断num的值来给nums数组赋值，循环结束之后为nums数组赋0。
class Solution {
public void moveZeroes(int[] nums) {
int i = 0;
for(int num : nums) {
if(num != 0) {
nums[i++] = num;
}
}
while(i < nums.length) {
nums[i++] = 0;
}
}
}
977.有序数组的平方
题目链接
给你一个按?非递减顺序?排序的整数数组?nums，返回?每个数字的平方?组成的新数组，要求也按?非递减顺序?排序。
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
方法一：冒泡排序法的思想
class Solution {
public int[] sortedSquares(int[] nums) {
int i = 0;
int temp;
for(int num : nums) {
nums[i++] = num * num;
}
for(int a = 0; a < nums.length-1; a++) {
for(int b = 0; b < nums.length-1; b++) {
if(nums[b+1] < nums[b]) {
temp = nums[b];
nums[b] = nums[b+1];
nums[b+1] = temp;
}
}
}
return nums;
}
}
方法二：从两边开始比较
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int point = right;
int[] arr = new int[nums.length];
while(left <= right) {
if((nums[right] *nums[right]) > (nums[left] * nums[left])) {
arr[point--] = nums[right] * nums[right];
right--;
}else {
arr[point--] = nums[left] * nums[left];
left++;
}
}
return arr;
}
}
方法三：从中间开始比较
找到第一个正数，把nums数组里的元素平方存到新的数组arr里，从第一个正数和最后一个负数的位置开始比较，最后判断剩下元素的情况（刚开始还一直以为只能返回数组nums，之后一看其他题解，都返回的新数组，5555~所以又重新写的第二种方法）
class Solution {
public int[] sortedSquares(int[] nums) {
int i = 0;
int[] arr = new int[nums.length];
// 找到第一个正数
for(int num : nums) {
if(num > 0)
break;
i++;
}
int right = i;
int left = i - 1;
i = 0;
// 把nums数组元素平方放到arr数组里
for(int num : nums) {
arr[i++] = num * num;
}
i = 0;
// 开始比较了
while(left >= 0 && right < nums.length) {
if(arr[right] < arr[left]) {
nums[i++] = arr[right++];
}else {
nums[i++] = arr[left--];
}
}
// 判断left和right有没有到头
if(left < 0) {
while(right < nums.length) {
nums[i++] = arr[right++];
}
}
if(right >= nums.length) {
while(left >= 0) {
nums[i++] = arr[left--];
}
}
return nums;
}
}
|