1. 数组的改变和移动总结
1.1 数组的改变
数组在内存中是一块连续的内存空间，我们可以直接通过下标进行访问，并进行修改。
在Java中，对于List类型来说，我们可以通过set(idx, element)方法将idx位置的元素进行修改。
1.2 数组的移动
数组的移动不能通过一条语句来实现，通常来说需要通过：插入、删除或者多次交换来实现。
1.3 数组的插入
数组的插入比较麻烦，我们想要在下标为k的位置插入一个元素时，首先需要将k及以后的元素往后移动一个位置，然后再将元素插入到k的位置处。
在Java中，对于List类型来说，我们可以通过add(idx, element)方法将元素添加到idx下标处。
1.4 数组的删除
删除下标为k的元素时，需要将k以后的元素向前移动一个位置。
对于List类型来说，我们可以通过remove(idx)方法删除下标为idx的元素。
2. 题目记录
453. ⭐最小操作次数使数组元素相等
分析题意
给你一个长度为 n的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
思路分析
这道题有一个很巧妙的思路：由于我们并不关心最终元素相等时的值而只关心操作的次数。所以我们可以将上述问题转化为：每次操作使一个元素减少1，返回让数组中所有元素相等的最小操作数。这样就简单了：我们想要操作数最小，就必须找到能使所有元素相等的最小值，其实这个值就是数组中的最小值。而操作的次数就是：每个数与最小值的差值之和。
class Solution {
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++){
min = Math.min(nums[i], min);
}
int ans = 0;
for(int i = 0; i < nums.length; i++){
ans = ans + nums[i] - min;
}
return ans;
}
}
那么正向思考这个问题应该怎么做呢？
注意到：每次操作都使n-1个数加1，也就是所每次操作都会使该数组的sum加上n-1。假设最小操作数为a次，那么此时一定有数学关系式：\(a(n-1) + sum = nx\)，其中x为最终数组中的值。
仅有这一个关系式的约束是不够的，我们还要想清楚的一点就是：原数组中最小的那个数需要操作a次才能够变为x ，即：\(min + a = x\) (这个比较难想明白)
根据这两个公式我们就可以求出最终的a了：\(a = sum - n * min\)
class Solution {
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
min = Math.min(nums[i], min);
}
return sum - nums.length * min;
}
}
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
665. 非递减数列
分析题意
给你一个长度为 n 的整数数组 nums，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。
思路分析
从前往后遍历，找到第一个 a > b的情况时，对a 或 b 的值进行修改，然后判断修改后的数组是否为非递减数组即可。关键在于：修改 a 还是 修改 b 呢？
这里其实是有两个选择的：
- 对于 [1, 3, 4, 2, 5] ，此时应该修改
b； - 对于[1, 3, 4, 3, 4], 此时应该修改
a；
一种简单的方法就是：我们两种情况都尝试，看看是否能够得到非递减数组。
class Solution {
public boolean checkPossibility(int[] nums) {
for(int i = 0; i < nums.length - 1; i++){
if(nums[i] > nums[i + 1]){
int n_1 = nums[i];
int n_2 = nums[i + 1];
// 修改a
nums[i] = n_2;
if(checkMethod(nums)) return true;
// 复位a
nums[i] = n_1;
// 修改b
nums[i + 1] = n_1;
if(checkMethod(nums)) return true;
return false;
}
}
return true;
}
boolean checkMethod(int[] nums){
for(int i = 1; i < nums.length; i++){
if(nums[i - 1] > nums[i]) return false;
}
return true;
}
}
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
283. 移动零
分析题意
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
关键点：保持非零元素的相对顺序。
思路分析
首先排除首尾双指针的思路，因为要保持非零元素的相对顺序，所以不能够使用首尾双指针来做。
首尾双指针是指：左指针找第一个0元素，右指针找第一个非0元素，然后交换两个元素。有点像归并排序。
由于不复制数组，所以大概率还是使用双指针来操作。分析一下，假设我们知道left左侧都是非零元素，然后在left右侧找到了一个非零元素，此时只需要将该元素放在left下标下即可。
基于此思路，我们用left来标识已经处理元素的右边界，然后通过右指针去寻找下一个非0元素，找到后放置在left位置并将left指针右移。
class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right = 0;
while(right < nums.length){
if(nums[right] != 0){
nums[left] = nums[right];
left ++;
}
right ++;
}
while(left < nums.length){
nums[left] = 0;
left ++;
}
}
}
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)