力扣-数组-数组的改变、移动
最小操作次数使数组元素相等(LeetCode453)
- 题目概述:给定一个长度为 n 的 非空 整数数组,每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
-
题目示例:
示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次操作(注意每次操作会增加两个元素的值):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
-
方法一:利用排序
利用排序再结合改进暴力法的思路,可以直接与数组中最小的进行比较,即排序过后的nums[0]
- JS代码
/**
* @param {number[]} nums
* @return {number}
*/
var minMoves = function(nums) {
nums.sort((a,b)=>a-b)
let count=0
nums.forEach((num)=> {
count+=num-nums[0]
})
return count
};
- Java代码
class Solution {
public int minMoves(int[] nums) {
Arrays.sort(nums);
int count=0;
for(int num:nums) {
count+=num-nums[0];
}
return count;
}
}
-
方法二:动态规划
如果对数组进行排序得到有序数列 a,可以有效地简化问题。考虑有序数组 a,我们不考虑整个问题,而是将问题分解。假设,直到 i-1 位置的元素都已经相等,我们只需要考虑 i 位的元素,将差值 diff=a[i]-a[i-1] 加到总移动次数上,使得第 i 位也相等。moves=moves+diff。
但当我们想要继续这一步时,a[i] 之后的元素也会被增加 diff,亦即 a[j]=a[j]+diff,其中 j>i。
但当实现本方法时,我们不需要对这样的 a[j] 进行增加。相反,我们把 moves 的数量增加到当前元素(a[i])中,a’[i]=a[i]+moves。
简而言之,我们对数列进行排序,一直更新 moves 以使得直到当前的元素相等,而不改变除了当前元素之外的元素。在整个数组扫描完毕后,moves 即为答案。
- java代码
public class Solution {
public int minMoves(int[] nums) {
Arrays.sort(nums);
int moves = 0;
for (int i = 1; i < nums.length; i++) {
int diff = (moves + nums[i]) - nums[i - 1];
//因为要和前一个进行比较,所以要进行数组的元素修改
//加过之后就等于前i-1位保持一致
nums[i] += moves;
//a[i] 之后的元素也会被增加 diff,所以move是累加的
moves += diff;
}
return moves;
}
}
非递减数列(LeetCode665)
-
题目概述:给你一个长度为 n 的整数数组,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]。
- 题目示例:
-
方法一:数组
首先思考问题:要使数组变成一个非递减数列,数组中至多有多少个 i 满足 nums[i]>nums[i+1]?——至多一个
但会出现一个问题,就是例如数组 [3,4,1,2],无论怎么修改也无法将其变成非递减数列,所以要对发现问题的数组进行修改然后进行判断是否满足要求
这时就会出现第二个问题,修改谁,修改为多少
第一种:可以将nums[i]修改成小于或等于nums[i+1]的数,又得保证nums[i]不小于前面的数,所以nums[i]越大越好,所以最好修改为nums[i+1]
第二种:同理可以修改nums[i+1]为nums[i]的值
注意:这里必须两种都要验证,否则就会出现考虑不周的现象,例如数组[4,2,3],数组[5,7,1,8]
- java代码
class Solution {
public boolean checkPossibility(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
int x = nums[i], y = nums[i + 1];
if (x > y) {
nums[i] = y;
if (isSorted(nums)) {
return true;
}
nums[i] = x; // 复原
nums[i + 1] = x;
return isSorted(nums);
}
}
return true;
}
public boolean isSorted(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; ++i) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
}
- JS代码
var checkPossibility = function(nums) {
const n = nums.length;
for (let i = 0; i < n - 1; ++i) {
const x = nums[i], y = nums[i + 1];
if (x > y) {
nums[i] = y;
if (isSorted(nums)) {
return true;
}
nums[i] = x; // 复原
nums[i + 1] = x;
return isSorted(nums);
}
}
return true;
};
const isSorted = (nums) => {
const n = nums.length;
for (let i = 1; i < n; ++i) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
-
方法二:数组优化
优化在减少多遍历nums数组
当nums[i]修改为nums[i+1]后,还需保证nums[i-1]<=nums[i],即要保证nums[i+1]>=nums[i-1],否则即要修改nums[i+1]为nums[i],接着判断后续数字的大小关系
- java代码
class Solution {
public boolean checkPossibility(int[] nums) {
int n = nums.length, cnt = 0;
for (int i = 0; i < n - 1; ++i) {
int x = nums[i], y = nums[i + 1];
if (x > y) {
cnt++;
if (cnt > 1) {
return false;
}
if (i > 0 && y < nums[i - 1]) {
nums[i + 1] = x;
}
}
}
return true;
}
}