LeetCode 2460: Apply Operations to an Array (Merge-Then-Compact Two Passes)
LeetCode 2460SimulationTwo PointersArrayToday we solve LeetCode 2460 - Apply Operations to an Array.
Source: https://leetcode.com/problems/apply-operations-to-an-array/
English
Problem Summary
Given an integer array nums, process it left to right:
1) If nums[i] == nums[i+1], double nums[i] and set nums[i+1] = 0.
2) After all operations, move all zeros to the end while preserving the order of non-zero values.
Key Insight
The operation naturally splits into two clean phases:
- Phase A (merge pass): simulate adjacent equal-pair merge once from left to right.
- Phase B (compact pass): stable-pack non-zero numbers to the front, fill the rest with zeros.
This avoids complicated in-place shifting during merges and keeps logic easy to verify.
Algorithm
1) For i = 0..n-2, if nums[i] == nums[i+1], do merge operation.
2) Create result array ans size n initialized to 0.
3) Scan nums; copy each non-zero into ans[write], increment write.
4) Return ans.
Complexity Analysis
Time: O(n).
Space: O(n) for output array (or O(1) extra if done fully in-place variant).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] applyOperations(int[] nums) {
int n = nums.length;
for (int i = 0; i + 1 < n; i++) {
if (nums[i] == nums[i + 1]) {
nums[i] *= 2;
nums[i + 1] = 0;
}
}
int[] ans = new int[n];
int w = 0;
for (int x : nums) {
if (x != 0) ans[w++] = x;
}
return ans;
}
}func applyOperations(nums []int) []int {
n := len(nums)
for i := 0; i+1 < n; i++ {
if nums[i] == nums[i+1] {
nums[i] *= 2
nums[i+1] = 0
}
}
ans := make([]int, n)
w := 0
for _, x := range nums {
if x != 0 {
ans[w] = x
w++
}
}
return ans
}class Solution {
public:
vector<int> applyOperations(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i + 1 < n; ++i) {
if (nums[i] == nums[i + 1]) {
nums[i] *= 2;
nums[i + 1] = 0;
}
}
vector<int> ans(n, 0);
int w = 0;
for (int x : nums) {
if (x != 0) ans[w++] = x;
}
return ans;
}
};from typing import List
class Solution:
def applyOperations(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n - 1):
if nums[i] == nums[i + 1]:
nums[i] *= 2
nums[i + 1] = 0
ans = [0] * n
w = 0
for x in nums:
if x != 0:
ans[w] = x
w += 1
return ansvar applyOperations = function(nums) {
const n = nums.length;
for (let i = 0; i + 1 < n; i++) {
if (nums[i] === nums[i + 1]) {
nums[i] *= 2;
nums[i + 1] = 0;
}
}
const ans = new Array(n).fill(0);
let w = 0;
for (const x of nums) {
if (x !== 0) ans[w++] = x;
}
return ans;
};中文
题目概述
给定整数数组 nums，按从左到右顺序处理：
1）若 nums[i] == nums[i+1]，则把 nums[i] 变成两倍，并把 nums[i+1] 置为 0。
2）所有操作完成后，把所有 0 移到数组末尾，同时保持非零元素相对顺序不变。
核心思路
这个题天然可以拆成两段：
- 第一段（合并）：单次线性扫描，处理相邻相等对。
- 第二段（压缩）：把非零值按原顺序写到前面，后面自动补 0。
拆段后逻辑清晰，不容易出现“边改边挪”导致的错位问题。
算法步骤
1）遍历 i=0..n-2，若 nums[i]==nums[i+1]，执行翻倍+置零。
2）新建答案数组 ans（初始全 0）。
3）再次遍历 nums，将非零元素依次写入 ans 前部。
4）返回 ans。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（使用返回数组；若采用原地写回可视作额外 O(1)）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] applyOperations(int[] nums) {
int n = nums.length;
for (int i = 0; i + 1 < n; i++) {
if (nums[i] == nums[i + 1]) {
nums[i] *= 2;
nums[i + 1] = 0;
}
}
int[] ans = new int[n];
int w = 0;
for (int x : nums) {
if (x != 0) ans[w++] = x;
}
return ans;
}
}func applyOperations(nums []int) []int {
n := len(nums)
for i := 0; i+1 < n; i++ {
if nums[i] == nums[i+1] {
nums[i] *= 2
nums[i+1] = 0
}
}
ans := make([]int, n)
w := 0
for _, x := range nums {
if x != 0 {
ans[w] = x
w++
}
}
return ans
}class Solution {
public:
vector<int> applyOperations(vector<int>& nums) {
int n = (int)nums.size();
for (int i = 0; i + 1 < n; ++i) {
if (nums[i] == nums[i + 1]) {
nums[i] *= 2;
nums[i + 1] = 0;
}
}
vector<int> ans(n, 0);
int w = 0;
for (int x : nums) {
if (x != 0) ans[w++] = x;
}
return ans;
}
};from typing import List
class Solution:
def applyOperations(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n - 1):
if nums[i] == nums[i + 1]:
nums[i] *= 2
nums[i + 1] = 0
ans = [0] * n
w = 0
for x in nums:
if x != 0:
ans[w] = x
w += 1
return ansvar applyOperations = function(nums) {
const n = nums.length;
for (let i = 0; i + 1 < n; i++) {
if (nums[i] === nums[i + 1]) {
nums[i] *= 2;
nums[i + 1] = 0;
}
}
const ans = new Array(n).fill(0);
let w = 0;
for (const x of nums) {
if (x !== 0) ans[w++] = x;
}
return ans;
};
Comments