3264. K 次乘运算后的最终数组 I

🟢   🔖  数组 数学 模拟 堆（优先队列）  🔗 力扣 LeetCode

题目

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.

Return an integer array denoting the final state of nums after performing all k operations.

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]

Example 2:

Input: nums = [1,2], k = 3, multiplier = 4

Output: [16,8]

Explanation:

Operation	Result
After operation 1	[4, 2]
After operation 2	[4, 8]
After operation 3	[16, 8]

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplier <= 5

题目大意

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

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

• 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
• 将 x 替换为 x * multiplier 。

请你返回执行完 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]

示例 2：

输入： nums = [1,2], k = 3, multiplier = 4

输出：[16,8]

解释：

操作	结果
1 次操作后	[4, 2]
2 次操作后	[4, 8]
3 次操作后	[16, 8]

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplier <= 5

解题思路

思路一：直接遍历法

1. 初始化操作次数 k 和倍乘因子 multiplier。
2. 循环 k 次：
   • 遍历 nums 数组，找到数组中最小值的索引。
   • 将该最小值更新为 x * multiplier。
3. 最终返回修改后的数组。

复杂度分析

• 时间复杂度：O(k * n)，每次查找最小值需要遍历数组，时间复杂度为 O(n)，一共执行 k 次，总时间复杂度为 O(k * n)。
• 空间复杂度：O(1)，仅使用了常数空间。

思路二：最小堆

1. 初始化最小堆 minHeap，最小堆的优先级为：按值从小到大排序，值相同时按索引排序。
2. 循环 k 次：
   • 从最小堆中取出堆顶元素 [num, idx]，也就是当前的 [最小值, 索引]。
   • 将该最小值更新为 [num * multiplier, idx]，并插入到堆中。
3. 将堆中数据按索引排序后，构建出仅含 num 的数组并返回。

复杂度分析

• 时间复杂度：O(n log n + k log n)
  • 初始构建堆的时间为 O(n)。
  • 每次弹出堆顶和插入的时间复杂度为 O(log n)，执行 k 次，复杂度为 O(k log n)。
  • 按索引排序的时间为 O(n log n)。
  • 总时间复杂度为 O(n log n + k log n)。
• 空间复杂度：O(n)，使用了堆存储 nums 的所有元素。

代码

直接遍历法

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} multiplier
 * @return {number[]}
 */
var multiplyMinimum = function (nums, k, multiplier) {
	for (let i = 0; i < k; i++) {
		// 找到当前数组的最小值索引
		let minIndex = 0;
		for (let j = 1; j < nums.length; j++) {
			if (nums[j] < nums[minIndex]) {
				minIndex = j;
			}
		}
		// 替换最小值
		nums[minIndex] *= multiplier;
	}
	return nums;
};

最小堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} multiplier
 * @return {number[]}
 */
var getFinalState = function (nums, k, multiplier) {
	// 构建 [num, idx] 数组
	const arr = nums.map((num, idx) => [num, idx]);
	// 按值排序，值相同时按索引排序
	const priority = (a, b) => {
		if (a[0] == b[0]) return a[1] < b[1];
		return a[0] < b[0];
	};

	// 初始化最小堆
	let minHeap = new MinHeap(arr, priority);

	while (k > 0) {
		// 获取当前最小值及其索引
		const [num, idx] = minHeap.pop();
		// 插入新的值到堆中
		minHeap.insert([num * multiplier, idx]);
		k--;
	}

	// 将堆中数据按 idx 排序后返回 num
	return minHeap
		.toArray()
		.sort((a, b) => a[1] - b[1]) // 按索引排序
		.map(([num, idx]) => num); // 构建仅含 num 的数组
};

// 最小堆
class MinHeap {
	constructor(arr = [], priority = (a, b) => a < b) {
		this.heap = arr;
		this.priority = priority;
		for (let i = ((this.heap.length / 2) | 0) - 1; i >= 0; i--) {
			this.heapifyDown(i);
		}
	}
	// 插入元素
	insert(item) {
		this.heap.push(item);
		this.heapifyUp(this.heap.length - 1);
	}
	// 移除并返回堆顶
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	toArray() {
		return this.heap;
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.priority(this.heap[i], this.heap[parent])) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let min = i;
		if (
			left < this.heap.length &&
			this.priority(this.heap[left], this.heap[min])
		) {
			min = left;
		}
		if (
			right < this.heap.length &&
			this.priority(this.heap[right], this.heap[min])
		) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
}