极大极小游戏

2293. 极大极小游戏

给你一个下标从 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] <= 10⁹
nums.length 是 2 的幂

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minMaxGame(vector<int>& nums) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 3.2 MB, 提交时间: 2023-01-15 12:38:19

func minMaxGame(nums []int) int {
	for n := len(nums); n > 1; {
		n >>= 1
		for i := 0; i < n; i++ {
			a, b := nums[i<<1], nums[i<<1|1]
			if i%2 == 0 {
				nums[i] = min(a, b)
			} else {
				nums[i] = max(a, b)
			}
		}
	}
	return nums[0]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2023-01-15 12:38:08

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        while n > 1:
            n >>= 1
            for i in range(n):
                a, b = nums[i << 1], nums[i << 1 | 1]
                nums[i] = min(a, b) if i % 2 == 0 else max(a, b)
        return nums[0]

java 解法, 执行用时: 1 ms, 内存消耗: 40.9 MB, 提交时间: 2023-01-15 12:37:50

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];
    }
}

javascript 解法, 执行用时: 60 ms, 内存消耗: 41.9 MB, 提交时间: 2023-01-15 12:37:38

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMaxGame = function(nums) {
    let n = nums.length;
    while (n !== 1) {
        const newNums = new Array(Math.floor(n / 2)).fill(0);
        for (let 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 = Math.floor(n / 2);
    }
    return nums[0];
};

javascript 解法, 执行用时: 64 ms, 内存消耗: 41.9 MB, 提交时间: 2023-01-15 12:34:56

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMaxGame = function(nums) {
    const n = nums.length;
    if (n === 1) {
        return nums[0];
    }
    const newNums = new Array(Math.floor(n / 2)).fill(0);
    for (let 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);
};

python3 解法, 执行用时: 36 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-15 12:34:41

# 递归
class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        newNums = [0] * (n // 2)
        for i in range(n // 2):
            if i % 2 == 0:
                newNums[i] = min(nums[2 * i], nums[2 * i + 1])
            else:
                newNums[i] = max(nums[2 * i], nums[2 * i + 1])
        return self.minMaxGame(newNums)

python3 解法, 执行用时: 36 ms, 内存消耗: 15.2 MB, 提交时间: 2022-06-06 14:55:06

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        while n != 1:
            newNums = []
            for i in range(0, n//2):
                if i % 2 == 0:
                    newNums.append(min(nums[2*i], nums[2*i+1]))
                else:
                    newNums.append(max(nums[2*i], nums[2*i+1]))
            nums = newNums
            n = len(nums)
        return nums[0]

上一题

下一题

详情