2293. 极大极小游戏

🟢   🔖  数组 模拟  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

1. Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.
2. For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
3. For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
4. Replace the array nums with newNums.
5. Repeat the entire process starting from step 1.

Return the last number that remains innums after applying the algorithm.

Example 1:

Input: nums = [1,3,5,2,4,8,2,2]

Output: 1

Explanation: The following arrays are the results of applying the algorithm repeatedly.

First: nums = [1,5,4,2]

Second: nums = [1,4]

Third: nums = [1]

1 is the last remaining number, so we return 1.

Example 2:

Input: nums = [3]

Output: 3

Explanation: 3 is already the last remaining number, so we return 3.

Constraints:

• 1 <= nums.length <= 1024
• 1 <= nums[i] <= 10^9
• nums.length is a power of 2.

题目大意

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。

对 nums 执行下述算法：

1. 设 n 等于 nums 的长度，如果 n == 1 ，终止 算法过程。否则，创建 一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
2. 对于满足 0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
3. 对于满足 0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
4. 用 newNums 替换 nums 。
5. 从步骤 1 开始 重复 整个过程。

执行算法后，返回 nums 中剩下的那个数字。

示例 1：

输入： nums = [1,3,5,2,4,8,2,2]

输出： 1

解释： 重复执行算法会得到下述数组。

第一轮：nums = [1,5,4,2]

第二轮：nums = [1,4]

第三轮：nums = [1]

1 是最后剩下的那个数字，返回 1 。

示例 2：

输入： nums = [3]

输出： 3

解释： 3 就是最后剩下的数字，返回 3 。

提示：

• 1 <= nums.length <= 1024
• 1 <= nums[i] <= 10^9
• nums.length 是 2 的幂

解题思路

1. 初始化变量 n 为数组的长度。

2. 使用一个 while 循环，当 n > 1 时进行迭代。

3. 在每轮中，遍历数组的前 n / 2 个元素，并根据规则替换其值：

   • 如果当前索引 i 是偶数，则取当前数组中第 2i 和 2i+1 个元素的最小值。
   • 如果当前索引 i 是奇数，则取当前数组中第 2i 和 2i+1 个元素的最大值。

4. 将 n 缩减为原来的一半。

5. 当n == 1 时，返回其唯一元素。

复杂度分析

• 时间复杂度：O(n)，每一轮的操作遍历一半的数组，直到数组长度减为 1，总操作次数为 n+n/2+n/4+…+1，这是一个等比数列，和为 O(n)。
• 空间复杂度：O(1)，使用了原地修改数组，未引入额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMaxGame = function (nums) {
	let n = nums.length;
	while (n > 1) {
		for (let i = 0; i < n / 2; i++) {
			if (i % 2 == 0) {
				nums[i] = Math.min(nums[i * 2], nums[i * 2 + 1]);
			} else {
				nums[i] = Math.max(nums[i * 2], nums[i * 2 + 1]);
			}
		}
		n /= 2; // 缩减数组长度
	}
	return nums[0];
};

相关题目

题号	标题	题解	标签	难度	力扣
390	消除游戏	[✓]	递归 数学	🟠	🀄️ 🔗
2221	数组的三角和		数组 数学 组合数学 1+	🟠	🀄️ 🔗