当前位置：首页 > news >正文

[leetcode][2293]极大极小游戏

news 来源：原创 2024/11/19 21:19:04

方法一：递归

思路与算法

按照题意构造下一级的数组
如果长度为1则返回

代码

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 < n / 2; i++) {
            if (i % 2 == 0) {
                newNums[i] = Math.min(nums[i * 2], nums[i * 2 + 1]);
            } else {
                newNums[i] = Math.max(nums[i * 2], nums[i * 2 + 1]);
            }
        }
        return minMaxGame(newNums);
    }
}

复杂度分析

时间复杂度：O(n)，每一轮需要 n / 2 + n / 4 + … + 1 = n
空间复杂度：O(n)，每个新数组的长度是 n / 2 + n / 4 + … + 1 = n

方法二：模拟

思路与算法

按照题意构造下一级的数组
如果长度为1则退出循环

代码

class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        while (n > 1) {
            int[] arr = new int[n / 2];
            for (int j = 0; j < n / 2; ++j) {
                if (j % 2 == 0) {
                    arr[j] = Math.min(nums[j * 2], nums[j * 2 + 1]);
                } else {
                    arr[j] = Math.max(nums[j * 2], nums[j * 2 + 1]);
                }
            }
            nums = arr;
            n /= 2;
        }
        return nums[0];
    }
}

复杂度分析

时间复杂度：O(n)，每一轮需要 n / 2 + n / 4 + … + 1 = n
空间复杂度：O(n)，每个新数组的长度是 n / 2 + n / 4 + … + 1 = n

方法三：原地修改

思路与算法

nums[i]一旦被用来计算下一层的值，没有其他地方会被用到。因此nums[i]可以被覆盖，无需新建数组
如果长度为1则退出循环

代码

class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        while (n > 1) {
            int m = n / 2;
            for (int j = 0; j < m; ++j) {
                if (j % 2 == 0) {
                    nums[j] = Math.min(nums[j * 2], nums[j * 2 + 1]);
                } else {
                    nums[j] = Math.max(nums[j * 2], nums[j * 2 + 1]);
                }
            }
            n = m;
        }
        return nums[0];
    }
}