极大极小游戏【LC2293】
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 in nums after applying the algorithm.
小年快乐~ 周赛在周六周日永远搞不清 周赛在周日周赛在周日周赛在周日
队列
- 思路：使用队列存放需要迭代的数组元素，并记录下标序号i，根据下标奇偶性取最大值最小值，每处理一组元素，序号加1，直至队列中只存在一个元素，返回即可。
。由于数组长度均为2 n ，迭代过程中长度一直为偶数直至长度为1，因此下标序号可以累计
- 实现
class Solution { public int minMaxGame(int[] nums) { Deque<Integer> deque = new LinkedList<>(); for (int num : nums){ deque.addLast(num); } int i = 0; while (deque.size() > 1){ if ((i & 1) == 0){ deque.addLast(Math.min(deque.pollFirst(),deque.pollFirst())); }else{ deque.addLast(Math.max(deque.pollFirst(),deque.pollFirst())); } i++; } return deque.pollFirst(); } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
构建数组
- 思路：构建新数组
- 实现
class Solution { public int minMaxGame(int[] nums) { int n = nums.length; while (n != 1) { int[] newNums = new int[n / 2]; for (int i = 0; i < newNums.length; i++) { if (i % 2 == 0) { newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]); } else { newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]); } } nums = newNums; n /= 2; } return nums[0]; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/min-max-game/solutions/2061544/ji-da-ji-xiao-you-xi-by-leetcode-solutio-ucpt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
递归
- 思路：若数组长度为1，那么返回nums[0]，否则，按照题意求出新数组，递归求解新数组的答案
- 实现
class Solution { public int minMaxGame(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; } int[] newNums = new int[n / 2]; for (int i = 0; i < newNums.length; i++) { if (i % 2 == 0) { newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]); } else { newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]); } } return minMaxGame(newNums); } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/min-max-game/solutions/2061544/ji-da-ji-xiao-you-xi-by-leetcode-solutio-ucpt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
原地修改
- 思路：数组中的元素被使用过就不再被使用，因此可以将第i ii对计算得到的结果，存储至nums[i]
- 实现
class Solution { public int minMaxGame(int[] nums) { int n = nums.length; while (n > 1){ for (int 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]; } }
。复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
