3266. K 次乘法运算后的最终数组状态 II

Hard

题目描述

给你一个整数数组 nums，一个整数 k 和一个整数 multiplier。

你需要对 nums 执行 k 次操作。在每次操作中：

找到 nums 中的最小值 x。如果最小值有多个，选择第一个出现的。
将选中的最小值 x 替换为 x * multiplier。

执行 k 次操作后，对 nums 中的每个值应用模 10^9 + 7。

返回一个整数数组，表示执行所有 k 次操作并应用模运算后 nums 的最终状态。

示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2
输出：[8,4,6,5,6]
解释：
操作 1 后：[2, 2, 3, 5, 6]
操作 2 后：[4, 2, 3, 5, 6]
操作 3 后：[4, 4, 3, 5, 6]
操作 4 后：[4, 4, 6, 5, 6]
操作 5 后：[8, 4, 6, 5, 6]
应用模运算后：[8, 4, 6, 5, 6]

示例 2：

输入：nums = [100000,2000], k = 2, multiplier = 1000000
输出：[999999307,999999993]

约束：

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^9
1 <= k <= 10^9
1 <= multiplier <= 10^6

解题思路

这道题需要分两个阶段来处理：

第一阶段：模拟阶段 当 min(nums) * multiplier <= max(nums) 时，我们需要逐次模拟操作。使用优先队列（最小堆）来高效地找到最小值和其索引。每次取出最小元素，乘以 multiplier 后重新放入堆中。

第二阶段：循环分配阶段
当 min(nums) * multiplier > max(nums) 时，说明进入了循环状态。此时所有元素都会按照索引顺序被依次操作。我们可以计算每个元素会被操作多少次完整轮次，以及剩余的操作次数如何分配。

关键优化点：

使用优先队列维护 (值, 索引) 对，确保找到字典序最小的元素
检测循环开始的时机，避免超时
使用快速幂计算大量重复乘法操作
及时应用模运算防止溢出

算法流程：

将数组元素和索引放入最小堆
模拟操作直到进入循环状态或操作完成
如果还有剩余操作，计算每个位置的额外乘法次数
使用快速幂计算最终结果并取模

代码实现

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        
        if (multiplier == 1) {
            return nums;
        }
        
        // 使用优先队列：{值, 索引}
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        
        for (int i = 0; i < n; i++) {
            pq.push({nums[i], i});
        }
        
        // 第一阶段：模拟直到 min * multiplier > max
        while (k > 0) {
            auto [minVal, minIdx] = pq.top();
            pq.pop();
            
            // 检查是否进入循环状态
            if (pq.empty() || minVal * multiplier > pq.top().first) {
                pq.push({minVal, minIdx});
                break;
            }
            
            pq.push({minVal * multiplier, minIdx});
            k--;
        }
        
        // 第二阶段：平均分配剩余操作
        if (k > 0) {
            int cycles = k / n;
            int remainder = k % n;
            
            // 快速幂函数
            auto power = [&](long long base, int exp) {
                long long result = 1;
                base %= MOD;
                while (exp > 0) {
                    if (exp & 1) result = (result * base) % MOD;
                    base = (base * base) % MOD;
                    exp >>= 1;
                }
                return result;
            };
            
            vector<pair<long long, int>> temp;
            while (!pq.empty()) {
                temp.push_back(pq.top());
                pq.pop();
            }
            
            for (int i = 0; i < n; i++) {
                long long val = temp[i].first;
                int idx = temp[i].second;
                
                // 每个元素都乘以 multiplier^cycles
                val = (val % MOD * power(multiplier, cycles)) % MOD;
                
                // 前 remainder 个元素额外乘以 multiplier
                if (i < remainder) {
                    val = (val * multiplier) % MOD;
                }
                
                nums[idx] = val;
            }
        } else {
            // 将堆中的结果写回数组
            while (!pq.empty()) {
                auto [val, idx] = pq.top();
                pq.pop();
                nums[idx] = val % MOD;
            }
        }
        
        return nums;
    }
};

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        MOD = 10**9 + 7
        n = len(nums)
        
        if multiplier == 1:
            return nums
        
        # 使用堆维护 (值, 索引)
        import heapq
        pq = [(nums[i], i) for i in range(n)]
        heapq.heapify(pq)
        
        # 第一阶段：模拟直到 min * multiplier > max
        while k > 0:
            min_val, min_idx = heapq.heappop(pq)
            
            # 检查是否进入循环状态
            if not pq or min_val * multiplier > pq[0][0]:
                heapq.heappush(pq, (min_val, min_idx))
                break
            
            heapq.heappush(pq, (min_val * multiplier, min_idx))
            k -= 1
        
        # 第二阶段：平均分配剩余操作
        if k > 0:
            cycles = k // n
            remainder = k % n
            
            # 快速幂
            def power(base, exp):
                result = 1
                base %= MOD
                while exp > 0:
                    if exp & 1:
                        result = (result * base) % MOD
                    base = (base * base) % MOD
                    exp >>= 1
                return result
            
            # 取出所有元素并排序
            temp = []
            while pq:
                temp.append(heapq.heappop(pq))
            
            for i in range(n):
                val, idx = temp[i]
                
                # 每个元素都乘以 multiplier^cycles
                val = (val % MOD * power(multiplier, cycles)) % MOD
                
                # 前 remainder 个元素额外乘以 multiplier
                if i < remainder:
                    val = (val * multiplier) % MOD
                
                nums[idx] = val
        else:
            # 将堆中的结果写回数组
            while pq:
                val, idx = heapq.heappop(pq)
                nums[idx] = val % MOD
        
        return nums

public class Solution {
    public int[] GetFinalState(int[] nums, int k, int multiplier) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        if (multiplier == 1) {
            return nums;
        }
        
        // 使用优先队列维护 (值, 索引)
        var pq = new PriorityQueue<(long val, int idx), (long val, int idx)>();
        
        for (int i = 0; i < n; i++) {
            pq.Enqueue((nums[i], i), (nums[i], i));
        }
        
        // 第一阶段：模拟直到 min * multiplier > max
        while (k > 0) {
            var (minVal, minIdx) = pq.Dequeue();
            
            // 检查是否进入循环状态
            if (pq.Count == 0 || minVal * multiplier > pq.Peek().val) {
                pq.Enqueue((minVal, minIdx), (minVal, minIdx));
                break;
            }
            
            pq.Enqueue((minVal * multiplier, minIdx), (minVal * multiplier, minIdx));
            k--;
        }
        
        // 第二阶段：平均分配剩余操作
        if (k > 0) {
            int cycles = k / n;
            int remainder = k % n;
            
            // 快速幂
            long Power(long baseVal, int exp) {
                long result = 1;
                baseVal %= MOD;
                while (exp > 0) {
                    if ((exp & 1) == 1) result = (result * baseVal) % MOD;
                    baseVal = (baseVal * baseVal) % MOD;
                    exp >>= 1;
                }
                return result;
            }
            
            var temp = new List<(long val, int idx)>();
            while (pq.Count > 0) {
                temp.Add(pq.Dequeue());
            }
            
            for (int i = 0; i < n; i++) {
                long val = temp[i].val;
                int idx = temp[i].idx;
                
                // 每个元素都乘以 multiplier^cycles
                val = (val % MOD * Power(multiplier, cycles)) % MOD;
                
                // 前 remainder 个元素额外乘以 multiplier
                if (i < remainder) {
                    val = (val * multiplier) % MOD;
                }
                
                nums[idx] = (int)val;
            }
        } else {
            // 将堆中的结果写回数组
            while (pq.Count > 0) {
                var (val, idx) = pq.Dequeue();
                nums[idx] = (int)(val % MOD);
            }
        }
        
        return nums;
    }
}

var getFinalState = function(nums, k, multiplier) {
    const MOD = 1000000007;
    const n = nums.length;
    
    if (multiplier === 1) {
        return nums.map(x => x % MOD);
    }
    
    // Create min heap with [value, index]
    const heap = nums.map((val, i) => [val, i]);
    heap.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    
    // Find max value in original array
    const maxVal = Math.max(...nums);
    
    // Simulate until all values reach maxVal or k operations done
    let operations = 0;
    while (operations < k && heap[0][0] < maxVal) {
        const [val, idx] = heap.shift();
        const newVal = val * multiplier;
        nums[idx] = newVal;
        
        // Insert back into heap maintaining order
        let insertPos = 0;
        while (insertPos < heap.length && 
               (heap[insertPos][0] < newVal || 
                (heap[insertPos][0] === newVal && heap[insertPos][1] < idx))) {
            insertPos++;
        }
        heap.splice(insertPos, 0, [newVal, idx]);
        
        operations++;
    }
    
    // If we still have operations left, distribute them evenly
    const remaining = k - operations;
    if (remaining > 0) {
        const fullCycles = Math.floor(remaining / n);
        const extraOps = remaining % n;
        
        // Apply full cycles to all elements
        if (fullCycles > 0) {
            const multiplierPower = modPow(multiplier, fullCycles, MOD);
            for (let i = 0; i < n; i++) {
                nums[i] = (nums[i] % MOD * multiplierPower) % MOD;
            }
        }
        
        // Apply extra operations to smallest elements
        for (let i = 0; i < extraOps; i++) {
            const idx = heap[i][1];
            nums[idx] = (nums[idx] % MOD * multiplier) % MOD;
        }
    }
    
    return nums.map(x => x % MOD);
};

function modPow(base, exp, mod) {
    let result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 === 1) {
            result = (result * base) % mod;
        }
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return result;
}

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析