【LetMeFly】3507.移除最小数对使数组有序 I：纯模拟
力扣题目链接：https://leetcode.cn/problems/minimum-pair-removal-to-sort-array-i/
给你一个数组 nums，你可以执行以下操作任意次数：
- 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
- 用它们的和替换这对元素。
返回将数组变为 非递减 所需的 最小操作次数 。
如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。
示例 1：
输入： nums = [5,2,3,1]
输出： 2
解释：
- 元素对
(3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
- 元素对
(2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。
示例 2：
输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。
提示：
1 <= nums.length <= 50-1000 <= nums[i] <= 1000
解题方法：模拟
写个函数判断是否已经非递减、写个函数判断哪个下标开始的数对被合并、写个函数合并两个数。
完事。
- 时间复杂度$O(len(nums)^2)$
- 空间复杂度$O(len(nums))$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
template<class Type>
void debug(vector<Type>v) {
for(int i = 0; i < v.size(); i++) {
cout << v[i] << ' ';
}
puts("");
}
class Solution {
private:
bool finished(vector<int>& nums) {
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[i - 1]) {
return false;
}
}
return true;
}
int getMinPairIdx(vector<int>& nums) {
int idx = 0, mini = 50001;
for (int i = 0; i + 1 < nums.size(); i++) {
int cnt = nums[i] + nums[i + 1];
if (cnt < mini) {
mini = cnt;
idx = i;
}
}
return idx;
}
vector<int> merge(vector<int>& nums, int idx) {
vector<int> ans;
for (int i = 0; i < idx; i++) {
ans.push_back(nums[i]);
}
ans.push_back(nums[idx] + nums[idx + 1]);
for (int i = idx + 2; i < nums.size(); i++) {
ans.push_back(nums[i]);
}
return ans;
}
public:
int minimumPairRemoval(vector<int>& nums) {
int ans = 0;
while (!finished(nums)) {
int idx = getMinPairIdx(nums);
nums = merge(nums, idx);
ans++;
}
return ans;
}
};
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
impl Solution {
fn finished(nums: &Vec<i32>) -> bool {
for i in 1..nums.len() {
if nums[i] < nums[i - 1] {
return false;
}
}
true
}
fn get_mini_pair_idx(nums: &Vec<i32>) -> usize {
let mut idx = 0;
let mut mini = 500001;
for i in 0..nums.len() - 1 {
let cnt = nums[i] + nums[i + 1];
if cnt < mini {
mini = cnt;
idx = i;
}
}
idx
}
fn merge(nums: &Vec<i32>, idx: usize) -> Vec<i32> {
let mut ans = Vec::with_capacity(nums.len() - 1);
for i in 0..idx {
ans.push(nums[i]);
}
ans.push(nums[idx] + nums[idx + 1]);
for i in idx + 2..nums.len() {
ans.push(nums[i]);
}
ans
}
pub fn minimum_pair_removal(mut nums: Vec<i32>) -> i32 {
let mut ans = 0;
while !Self::finished(&nums) {
let idx = Self::get_mini_pair_idx(&nums);
nums = Self::merge(&nums, idx);
ans += 1;
}
ans
}
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源