請用 C/C++ 寫 You are given an integer array nums, an integer k, and an integer multiplier.…
- User
請用 C/C++ 寫 You are given an integer array nums, an integer k, and an integer multiplier.
You need to perform k operations on nums. In each operation:
Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first. Replace the selected minimum value x with x * multiplier. After the k operations, apply modulo 109 + 7 to every value in nums.
Return an integer array denoting the final state of nums after performing all k operations and then applying the modulo.
Example 1:
Input: nums = [2,1,3,5,6], k = 5, multiplier = 2
Output: [8,4,6,5,6]
Explanation:
Operation Result After operation 1 [2, 2, 3, 5, 6] After operation 2 [4, 2, 3, 5, 6] After operation 3 [4, 4, 3, 5, 6] After operation 4 [4, 4, 6, 5, 6] After operation 5 [8, 4, 6, 5, 6] After applying modulo [8, 4, 6, 5, 6] Example 2:
Input: nums = [100000,2000], k = 2, multiplier = 1000000
Output: [999999307,999999993]
Explanation:
Operation Result After operation 1 [100000, 2000000000] After operation 2 [100000000000, 2000000000] After applying modulo [999999307, 999999993]
Constraints:
1 <= nums.length <= 104 1 <= nums[i] <= 109 1 <= k <= 109 1 <= multiplier <= 106 實做以下 class class Solution { public: vector getFinalState(vector& nums, int k, int multiplier) {
}};
- Assistant
To solve this problem efficiently, we need to process the
koperations in batches rather than simulating each operation individually, askcan be up to (10^9) and the array size up to (10^4). Here's how we can do it:-
Use a Multiset or Map: We use a multiset (or a map) to store the current values of the array elements along with their indices. This allows us to efficiently find the minimum value and handle multiple elements with the same value.
-
Batch Process Elements: We process all elements with the current minimum value together. We determine how many times (
times) we can multiply these elements bymultiplierbefore their value reaches or exceeds the next minimum value in the set or we run out ofkoperations. -
Calculate the Number of Mulitiplications (
t): We calculatet, the minimal number of times we need to multiply the current min value bymultiplierto reach the next min value. Whenmultiplier > 1, we can computetusing logarithms without floating-point errors by using integer logarithms or iteration sincemultiplierand initial values have limits. -
Update the Elements: We update all the elements with the current minimum value by multiplying them by
multiplier^timesand reducekbytimes * number of elements with current min value. -
Repeat Until
kis Exhausted: We repeat steps 2-4 until we have performedkoperations. -
Apply Modulo and Prepare the Result: After all operations, we apply the modulo (10^9 + 7) to every number as required and return the final array.
Here's the C++ code implementing the above approach:
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <set> using namespace std; class Solution { public: vector<int> getFinalState(vector<int>& nums, int k, int multiplier) { int n = nums.size(); const int MOD = 1e9 + 7; // Store the current values and their indices vector<long long> current_values(nums.begin(), nums.end()); // For storing the counts of multiplications for each index vector<long long> counts(n, 0); // Set for current values and their indices (value, index) // Using a set to keep it sorted set<pair<long long, int>> s; for (int i = 0; i < n; ++i) { s.insert({current_values[i], i}); } while (k > 0) { // Get the minimal value auto it = s.begin(); long long v_min = it->first; // Get indices of elements with minimal value vector<int> idxs; auto range = s.equal_range({v_min, -1}); for (auto itr = range.first; itr != range.second; ++itr) { idxs.push_back(itr->second); } int n_min = idxs.size(); // Get the next minimal value long long v_next = LLONG_MAX; auto it_next = it; ++it_next; if (it_next != s.end()) { v_next = it_next->first; } long long t = 0; if (multiplier == 1) { if (v_min >= v_next) { t = 0; } else { t = LLONG_MAX; // infinity } } else { // t is the minimal integer satisfying v_min * multiplier^t >= v_next long long m = multiplier; t = 0; long long v = v_min; while (v < v_next) { v *= m; ++t; if (t > 60) { // Since multiplier^60 is already huge break; } } if (t > 60) t = LLONG_MAX; // infinity } // Compute times long long times = min(k / n_min, t); if (times == 0) times = 1; // At least process once if k >= n_min if (times * n_min > k) times = k / n_min; if (times == 0) times = 1; // Update k long long total_ops = times * n_min; if (total_ops > k) total_ops = k; k -= total_ops; // Update the elements // Remove the old values from the set and insert the new values for (int idx : idxs) { s.erase({ current_values[idx], idx }); counts[idx] += times; current_values[idx] = current_values[idx] * pow(multiplier, times); s.insert({ current_values[idx], idx }); } } // Apply modulo and prepare the result vector<int> result(n); const int MODULAR = 1e9 + 7; for (int i = 0; i < n; ++i) { // nums[i] * multiplier^counts[i] mod (1e9 + 7) long long value = nums[i]; long long power = counts[i]; long long m = 1; const long long modulo = 1e9 + 7; long long mult = multiplier % modulo; // Fast exponentiation while (power > 0) { if (power % 2 == 1) m = (m * mult) % modulo; mult = (mult * mult) % modulo; power /= 2; } value = (value % modulo) * m % modulo; result[i] = (int)value; } return result; } };Explanation of the Code:
- The function
getFinalStateperforms the required operations. - We use a
setto keep the elements in a sorted order with their indices, which helps in quickly finding the minimal value. - We calculate the number of times (
times) we can batch process all minimal elements before their value reaches or exceeds the next minimal value or we exhaustk. - We update the values and counts of the minimal elements and update the set accordingly.
- After processing all operations, we compute the final values by exponentiating the multiplier to the counts and multiplying with the original numbers, applying modulo at the end.
This implementation effectively reduces the number of iterations by processing multiple elements at once and should work efficiently within the given constraints.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.