3810. Minimum Operations to Reach Target Array

📘 題目敘述

給定兩個整數陣列 nums 與 target，長度皆為 n，其中 nums[i] 是索引 i 目前的值，而 target[i] 是索引 i 想要變成的值。

你可以進行以下操作任意次（包含 0 次）：

選擇一個整數值 x
找出所有最大連續區段，使得區段內 nums[i] == x （區段為 maximal 表示不能再往左或往右延伸仍保持值都等於 x）
對每個這樣的區段 [l, r]，同時更新：
- nums[l] = target[l]
- nums[l + 1] = target[l + 1]
- ...
- nums[r] = target[r]

請回傳將 nums 變成 target 所需的最少操作次數。

條件限制

1 <= n == nums.length == target.length <= 10^5
1 <= nums[i], target[i] <= 10^5

🧠 解題思路

我抓到這題操作的本質是：

一次操作只能選一個值 x
而且一次操作只會影響「目前 nums[i] == x」的那些位置（不管它們分成幾段，符合 x 的段都會一起被更新）

所以我就把問題轉成在想：

哪些位置 i 其實需要被改（nums[i] != target[i]）
在這些需要被改的位置裡，nums[i] 出現了幾種不同的值

因為只要某個值 x 出現在「需要修正的位置」中：

那些位置一定要靠「選擇 x」的操作才會被更新
不選 x，那些位置永遠不會被動到

因此我的結論就是：

最少操作次數 = 在所有 nums[i] != target[i] 的位置中，nums[i] 的不同值數量

所有變數

seen：用來記錄「某個數值 x 是否已經算過一次操作」
n：陣列長度
ans：累計最少操作次數（也就是不同值的數量）

🪜 主要流程步驟

掃描所有位置

我從左到右掃過每個索引 i：

若 nums[i] == target[i] 代表這個位置本來就是對的，不需要處理
若 nums[i] != target[i] 代表這個位置一定需要被某次操作更新這時我就去看它目前的值 nums[i]

統計「需要被處理的值」有幾種

對於每個 nums[i] != target[i] 的位置：

如果 seen[nums[i]] == false 代表這個值是第一次出現在「需要被修正的位置」 → 我就：
- ans++（表示至少需要一次選這個值的操作）
- seen[nums[i]] = true（避免重複計數）
如果 seen[nums[i]] == true 代表之前已經算過這個值了 → 不需要再增加操作次數

最後回傳

掃完後 ans 就是最少操作次數，直接回傳。

💻 程式碼實作

class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& target) {

        
        bool seen[100001] = {false};
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != target[i]) {
                if (!seen[nums[i]]) {
                    ans++;
                    seen[nums[i]] = true;
                }
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimum-operations-to-reach-target-array/