You are given a 0-indexed array nums
of size n
consisting of non-negative integers.
You need to apply n - 1
operations to this array where, in the ith
operation (0-indexed), you will apply the following on the ith
element of nums
:
- If
nums[i] == nums[i + 1]
, then multiplynums[i]
by2
and setnums[i + 1]
to0
. Otherwise, you skip this operation.
After performing all the operations, shift all the 0
's to the end of the array.
- For example, the array
[1,0,2,0,0,1]
after shifting all its0
's to the end, is[1,2,1,0,0,0]
.
Return the resulting array.
Note that the operations are applied sequentially, not all at once.
Example 1:
Input: nums = [1,2,2,1,1,0] Output: [1,4,2,0,0,0] Explanation: We do the following operations: - i = 0: nums[0] and nums[1] are not equal, so we skip this operation. - i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,4,0,1,1,0]. - i = 2: nums[2] and nums[3] are not equal, so we skip this operation. - i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,2,0,0]. - i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,0,0]. After that, we shift the 0's to the end, which gives the array [1,4,2,0,0,0].
Example 2:
Input: nums = [0,1] Output: [1,0] Explanation: No operation can be applied, we just shift the 0 to the end.
Constraints:
2 <= nums.length <= 2000
0 <= nums[i] <= 1000
对数组执行操作。
给你一个下标从 0 开始的数组 nums ,数组大小为 n ,且由 非负 整数组成。
你需要对数组执行 n - 1 步操作,其中第 i 步操作(从 0 开始计数)要求对 nums 中第 i 个元素执行下述指令:
如果 nums[i] == nums[i + 1] ,则 nums[i] 的值变成原来的 2 倍,nums[i + 1] 的值变成 0 。否则,跳过这步操作。
在执行完 全部 操作后,将所有 0 移动 到数组的 末尾 。例如,数组 [1,0,2,0,0,1] 将所有 0 移动到末尾后变为 [1,2,1,0,0,0] 。
返回结果数组。注意 操作应当 依次有序 执行,而不是一次性全部执行。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/apply-operations-to-an-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是追击型双指针,如果没有做过283题,建议先做一下,本题跟283题几乎一样。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int[] applyOperations(int[] nums) { 3 int n = nums.length; 4 for (int i = 0; i < n - 1; i++) { 5 if (nums[i] == nums[i + 1]) { 6 nums[i] = nums[i] * 2; 7 nums[i + 1] = 0; 8 } 9 } 10 11 int cur = 0; 12 for (int i = 0; i < n; i++) { 13 if (nums[i] != 0) { 14 nums[cur] = nums[i]; 15 cur++; 16 } 17 } 18 while (cur < n) { 19 nums[cur] = 0; 20 cur++; 21 } 22 return nums; 23 } 24 }
相关题目
2460. Apply Operations to an Array
- Operations LeetCode Apply Array 2460operations leetcode apply array operations palindrome leetcode array 数组leetcode 2460 codeforces operations array round operations leetcode minimum halve operations leetcode applying maximal leetcode original prefix array leetcode winner array 1535 leetcode mountain index array partition leetcode check array