Skip to content

Files

Latest commit

 

History

History
186 lines (148 loc) · 4.57 KB

File metadata and controls

186 lines (148 loc) · 4.57 KB

English Version

题目描述

给你一个下标从 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] <= 109
  • nums.length2 的幂

解法

方法一:模拟

Python3

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        t = []
        for i in range(n >> 1):
            v = (
                max(nums[i << 1], nums[i << 1 | 1])
                if i & 1
                else min(nums[i << 1], nums[i << 1 | 1])
            )
            t.append(v)
        return self.minMaxGame(t)

Java

class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] t = new int[n >> 1];
        for (int i = 0; i < t.length; ++i) {
            int a = nums[i << 1], b = nums[i << 1 | 1];
            t[i] = (i & 1) == 1 ? Math.max(a, b) : Math.min(a, b);
        }
        return minMaxGame(t);
    }
}

C++

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        vector<int> t(n >> 1);
        for (int i = 0; i < t.size(); ++i) {
            int a = nums[i << 1], b = nums[i << 1 | 1];
            t[i] = (i & 1) == 1 ? max(a, b) : min(a, b);
        }
        return minMaxGame(t);
    }
};

Go

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

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

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

TypeScript

function minMaxGame(nums: number[]): number {
    while (nums.length > 1) {
        let n = nums.length;
        let tmp = [];
        for (let i = 0; i < n; i += 2) {
            if (i % 4 == 2) {
                tmp.push(Math.max(nums[i], nums[i + 1]));
            } else {
                tmp.push(Math.min(nums[i], nums[i + 1]));
            }
        }
        nums = tmp;
    }
    return nums[0];
}

...