LeetCode 2293. 极大极小游戏
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
【LetMeFly】2293.极大极小游戏
力扣题目链接https://leetcode.cn/problems/min-max-game/
给你一个下标从 0 开始的整数数组 nums
其长度是 2
的幂。
对 nums
执行下述算法
- 设
n
等于nums
的长度如果n == 1
终止 算法过程。否则创建 一个新的整数数组newNums
新数组长度为n / 2
下标从 0 开始。 - 对于满足
0 <= i < n / 2
的每个 偶数 下标i
将newNums[i]
赋值 为min(nums[2 * i], nums[2 * i + 1])
。 - 对于满足
0 <= i < n / 2
的每个 奇数 下标i
将newNums[i]
赋值 为max(nums[2 * i], nums[2 * i + 1])
。 - 用
newNums
替换nums
。 - 从步骤 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] <= 109
nums.length
是2
的幂
方法一递归
如果数组nums中只有一个元素那么直接返回这个元素就是答案。
否则我们需要创建一个新的数组将原始数组两两取最大最小后添加到新的数组中。
这样操作后我们就得到了新的数组。接下来递归调用这个函数计算新数组的再新数组直到长度为1直接返回数组中的唯一元素为止。
- 时间复杂度 O ( n ) O(n) O(n)其中 n = l e n ( n u m s ) n=len(nums) n=len(nums)。 O ( n ) + O ( n 2 ) + O ( n 4 ) + ⋯ + O ( 1 ) = O ( n ) O(n)+O(\frac{n}{2})+O(\frac{n}{4})+\cdots+O(1)=O(n) O(n)+O(2n)+O(4n)+⋯+O(1)=O(n)
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
class Solution {
public:
int minMaxGame(vector<int>& nums) {
if (nums.size() == 1)
return nums[0];
vector<int> newNum;
int loc = 0;
bool isMin = true;
while (loc < nums.size()) {
if (isMin) {
newNum.push_back(min(nums[loc++], nums[loc++]));
isMin = false;
}
else {
newNum.push_back(max(nums[loc++], nums[loc++]));
isMin = true;
}
}
return minMaxGame(newNum);
}
};
Python
class Solution:
def minMaxGame(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
newNum = []
loc = 0
isMin = True
while loc < len(nums):
if isMin:
newNum.append(min(nums[loc], nums[loc + 1]))
isMin = False
else:
newNum.append(max(nums[loc], nums[loc + 1]))
isMin = True
loc += 2
return self.minMaxGame(newNum)
同步发文于CSDN原创不易转载请附上原文链接哦~
Tisfyhttps://letmefly.blog.csdn.net/article/details/128691681