登录
3507. 移除最小数对使数组有序 I
2025年4月7日 06:11
解法一
思路和算法
如果初始时数组 $\textit{nums}$ 已经非递减，则最小操作次数是 $0$。以下只考虑初始时数组 $\textit{nums}$ 不满足非递减的情况。
最直观的思路是模拟数组的操作。每次操作时，遍历数组 $\textit{nums}$ 寻找相邻元素对中的元素和最小且最左边的一个元素对，用元素和替换这对元素，直到数组变成非递减，此时的操作次数即为将数组变为非递减所需的最小操作次数。
用 $n$ 表示数组 $\textit{nums}$ 的长度。由于每次操作之后都会将数组中的元素个数减少 $1$，因此每次操作应将执行合并操作的元素对右侧的元素向左移动。对于 $0 \le k < n$ 的整数 $k$，在执行 $k$ 次操作之后，剩余元素个数是 $n - k$，因此下一次操作时应只考虑数组的前 $n - k$ 个元素。
代码
###Java
class Solution {
public int minimumPairRemoval(int[] nums) {
int removals = 0;
int n = nums.length;
while (!isNonDecreasing(nums, n)) {
update(nums, n);
removals++;
n--;
}
return removals;
}
public void update(int[] nums, int n) {
int minSum = Integer.MAX_VALUE;
int index = -1;
for (int i = 0; i < n - 1; i++) {
if (nums[i] + nums[i + 1] < minSum) {
minSum = nums[i] + nums[i + 1];
index = i;
}
}
if (index >= 0) {
nums[index] = minSum;
for (int i = index + 1; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
}
}
public boolean isNonDecreasing(int[] nums, int n) {
for (int i = 1; i < n; i++) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
}
###C#
public class Solution {
public int MinimumPairRemoval(int[] nums) {
int removals = 0;
int n = nums.Length;
while (!IsNonDecreasing(nums, n)) {
Update(nums, n);
removals++;
n--;
}
return removals;
}
public void Update(int[] nums, int n) {
int minSum = int.MaxValue;
int index = -1;
for (int i = 0; i < n - 1; i++) {
if (nums[i] + nums[i + 1] < minSum) {
minSum = nums[i] + nums[i + 1];
index = i;
}
}
if (index >= 0) {
nums[index] = minSum;
for (int i = index + 1; i < n - 1; i++) {
nums[i] = nums[i + 1];
}
}
}
public bool IsNonDecreasing(int[] nums, int n) {
for (int i = 1; i < n; i++) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
}
复杂度分析
-
时间复杂度：$O(n^2)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。最差情况需要执行 $n - 1$ 次操作，每次操作的时间是 $O(n)$，因此时间复杂度是 $O(n^2)$。
-
空间复杂度：$O(1)$。所有的操作均为原地修改数组。
解法二
思路和算法
使用双向链表、哈希表和优先队列，可以将时间复杂度降低到 $O(n \log n)$。具体见题解「3510. 移除最小数对使数组有序 II」。
代码
###Java
class Solution {
private class Node {
private int index;
private long value;
private Node prev;
private Node next;
public Node() {
this(-1, Integer.MAX_VALUE);
}
public Node(int index, long value) {
this.index = index;
this.value = value;
prev = null;
next = null;
}
public int getIndex() {
return index;
}
public long getValue() {
return value;
}
public void setValue(long value) {
this.value = value;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public int minimumPairRemoval(int[] nums) {
int removals = 0;
Map<Integer, Node> indexToNode = new HashMap<Integer, Node>();
Node pseudoHead = new Node();
Node pseudoTail = new Node();
Node prevNode = pseudoHead;
int n = nums.length;
for (int i = 0; i < n; i++) {
Node node = new Node(i, nums[i]);
indexToNode.put(i, node);
prevNode.setNext(node);
node.setPrev(prevNode);
prevNode = node;
}
prevNode.setNext(pseudoTail);
pseudoTail.setPrev(prevNode);
PriorityQueue<long[]> pq = new PriorityQueue<long[]>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
int reversePairs = 0;
for (int i = 0; i < n - 1; i++) {
pq.offer(new long[]{nums[i] + nums[i + 1], i, i + 1});
if (nums[i] > nums[i + 1]) {
reversePairs++;
}
}
while (reversePairs > 0) {
long[] arr = pq.poll();
long newValue = arr[0];
int index1 = (int) arr[1], index2 = (int) arr[2];
if (!indexToNode.containsKey(index1) || !indexToNode.containsKey(index2) || newValue != indexToNode.get(index1).getValue() + indexToNode.get(index2).getValue()) {
continue;
}
removals++;
Node node1 = indexToNode.get(index1), node2 = indexToNode.get(index2);
if (node1.getValue() > node2.getValue()) {
reversePairs--;
}
if (node1.getPrev().getIndex() >= 0 && node1.getPrev().getValue() > node1.getValue()) {
reversePairs--;
}
if (node2.getNext().getIndex() >= 0 && node2.getNext().getValue() < node2.getValue()) {
reversePairs--;
}
node1.setValue(newValue);
remove(node2);
indexToNode.remove(index2);
if (node1.getPrev().getIndex() >= 0) {
pq.offer(new long[]{node1.getPrev().getValue() + node1.getValue(), node1.getPrev().getIndex(), node1.getIndex()});
if (node1.getPrev().getValue() > node1.getValue()) {
reversePairs++;
}
}
if (node1.getNext().getIndex() >= 0) {
pq.offer(new long[]{node1.getValue() + node1.getNext().getValue(), node1.getIndex(), node1.getNext().getIndex()});
if (node1.getNext().getValue() < node1.getValue()) {
reversePairs++;
}
}
}
return removals;
}
public void remove(Node node) {
Node prev = node.getPrev(), next = node.getNext();
prev.setNext(next);
next.setPrev(prev);
}
}
###C#
public class Solution {
public class Node {
public int Index { get; set; }
public long Value { get; set; }
public Node Prev { get; set; }
public Node Next { get; set; }
public Node() : this(-1, int.MaxValue) {
}
public Node(int index, long value) {
Index = index;
Value = value;
Prev = null;
Next = null;
}
}
public int MinimumPairRemoval(int[] nums) {
int removals = 0;
IDictionary<int, Node> indexToNode = new Dictionary<int, Node>();
Node pseudoHead = new Node();
Node pseudoTail = new Node();
Node prevNode = pseudoHead;
int n = nums.Length;
for (int i = 0; i < n; i++) {
Node node = new Node(i, nums[i]);
indexToNode.Add(i, node);
prevNode.Next = node;
node.Prev = prevNode;
prevNode = node;
}
prevNode.Next = pseudoTail;
pseudoTail.Prev = prevNode;
Comparer<Tuple<long, int, int>> comparer = Comparer<Tuple<long, int, int>>.Create((a, b) => a.Item1 != b.Item1 ? a.Item1.CompareTo(b.Item1) : a.Item2.CompareTo(b.Item2));
PriorityQueue<Tuple<long, int, int>, Tuple<long, int, int>> pq = new PriorityQueue<Tuple<long, int, int>, Tuple<long, int, int>>(comparer);
int reversePairs = 0;
for (int i = 0; i < n - 1; i++) {
pq.Enqueue(new Tuple<long, int, int>(nums[i] + nums[i + 1], i, i + 1), new Tuple<long, int, int>(nums[i] + nums[i + 1], i, i + 1));
if (nums[i] > nums[i + 1]) {
reversePairs++;
}
}
while (reversePairs > 0) {
Tuple<long, int, int> tuple = pq.Dequeue();
long newValue = tuple.Item1;
int index1 = tuple.Item2, index2 = tuple.Item3;
if (!indexToNode.ContainsKey(index1) || !indexToNode.ContainsKey(index2) || newValue != indexToNode[index1].Value + indexToNode[index2].Value) {
continue;
}
removals++;
Node node1 = indexToNode[index1], node2 = indexToNode[index2];
if (node1.Value > node2.Value) {
reversePairs--;
}
if (node1.Prev.Index >= 0 && node1.Prev.Value > node1.Value) {
reversePairs--;
}
if (node2.Next.Index >= 0 && node2.Next.Value < node2.Value) {
reversePairs--;
}
node1.Value = newValue;
Remove(node2);
indexToNode.Remove(index2);
if (node1.Prev.Index >= 0) {
pq.Enqueue(new Tuple<long, int, int>(node1.Prev.Value + node1.Value, node1.Prev.Index, node1.Index), new Tuple<long, int, int>(node1.Prev.Value + node1.Value, node1.Prev.Index, node1.Index));
if (node1.Prev.Value > node1.Value) {
reversePairs++;
}
}
if (node1.Next.Index >= 0) {
pq.Enqueue(new Tuple<long, int, int>(node1.Value + node1.Next.Value, node1.Index, node1.Next.Index), new Tuple<long, int, int>(node1.Value + node1.Next.Value, node1.Index, node1.Next.Index));
if (node1.Next.Value < node1.Value) {
reversePairs++;
}
}
}
return removals;
}
public void Remove(Node node) {
Node prev = node.Prev, next = node.Next;
prev.Next = next;
next.Prev = prev;
}
}
复杂度分析
-
时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。遍历数组初始化数据结构的时间是 $O(n \log n)$，最差情况需要执行 $n - 1$ 次操作，每次操作中的双向链表和哈希表的更新时间是 $O(1)$，优先队列的更新时间是 $O(\log n)$，因此时间复杂度是 $O(n \log n)$。
-
空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。双向链表、哈希表和优先队列的空间是 $O(n)$。
