2293-极大极小游戏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

方法一：递归

思路与算法

若数组 nums 的长度 n 等于 1，我们直接返回 nums}[0] 作为答案。否则，按照题意求出一个长度为 \dfrac{n}{2 的数组 newNums，递归求解 newNums 的答案即可。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
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)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }
        vector<int> newNums(n / 2);
        for (int i = 0; i < newNums.size(); i++) {
            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 minMaxGame(newNums);
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public 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);
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int minMaxGame(int* nums, int numsSize) {
    if (numsSize == 1) {
        return nums[0];
    }

    numsSize /= 2;
    int newNums[numsSize];
    for (int i = 0; i < numsSize; i++) {
        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 minMaxGame(newNums, numsSize);
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。递归的每一层时间复杂度为 O(n)，每次递归到下一层时问题规模减半，所以总体复杂度为 O(n) + O(\dfrac{n}{2}) + O(\dfrac{n}{4}) + \cdots + O(1) = O(n)。

  • 空间复杂度：O(n)，其中 n 是数组 nums 的长度。递归的每一层空间复杂度为 O(n)，每次递归到下一层时问题规模减半，所以总体复杂度为 O(n) + O(\dfrac{n}{2}) + O(\dfrac{n}{4}) + \cdots + O(1) = O(n)。除此之外，递归的栈空间为 O(\log n)，故总体复杂度为 O(n)。

方法二：模拟

思路与算法

我们用一个循环来模拟整个过程，循环的条件是 n \neq 1，其中 n 是 nums 的长度。循环内，我们按照题意求出 newNums，然后用 newNums 替换 nums 即可。最后返回 nums}[0] 作为答案。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        int n = nums.size();
        while (n != 1) {
            vector<int> newNums(n / 2);
            for (int i = 0; i < newNums.size(); i++) {
                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]);
                }
            }
            nums = newNums;
            n /= 2;
        }
        return nums[0];
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public 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];
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int minMaxGame(int* nums, int numsSize) {
    while (numsSize != 1) {
        numsSize /= 2;
        int newNums[numsSize];
        for (int i = 0; i < numsSize; i++) {
            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]);
            }
        }
        memcpy(nums, newNums, sizeof(int) * numsSize);
    }
    return nums[0];
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。第一次循环的时间复杂度为 O(n)，下一次循环时问题规模减半，所以总体复杂度为 O(n) + O(\dfrac{n}{2}) + O(\dfrac{n}{4}) + \cdots + O(1) = O(n)。

  • 空间复杂度：O(n)，其中 n 是数组 nums 的长度。

方法三：原地修改

思路与算法

注意到在顺序遍历的情况下，newNums}[i] 的计算结果可以直接存储到 nums}[i] 中。这是因为 nums}[i] 早在计算 newNums}[\Big\lfloor \dfrac{i}{2} \Big\rfloor] 时就已经被使用，而且它在未来一定不会再被使用。有一个特例是 i = 0，但此时可以原地修改的原因是很显然的。

代码

[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        int n = nums.size();
        while (n != 1) {
            int m = n / 2;
            for (int i = 0; i < m; i++) {
                if (i % 2 == 0) {
                    nums[i] = min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    nums[i] = max(nums[2 * i], nums[2 * i + 1]);
                }
            }
            n = m;
        }
        return nums[0];
    }
};
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        while (n != 1) {
            int m = n / 2;
            for (int i = 0; i < m; i++) {
                if (i % 2 == 0) {
                    nums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    nums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
                }
            }
            n = m;
        }
        return nums[0];
    }
}
[sol3-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int MinMaxGame(int[] nums) {
        int n = nums.Length;
        while (n != 1) {
            int m = n / 2;
            for (int i = 0; i < m; i++) {
                if (i % 2 == 0) {
                    nums[i] = Math.Min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    nums[i] = Math.Max(nums[2 * i], nums[2 * i + 1]);
                }
            }
            n = m;
        }
        return nums[0];
    }
}
[sol3-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int minMaxGame(int* nums, int numsSize) {
    while (numsSize != 1) {
        numsSize /= 2;
        for (int i = 0; i < numsSize; i++) {
            if (i % 2 == 0) {
                nums[i] = MIN(nums[2 * i], nums[2 * i + 1]);
            } else {
                nums[i] = MAX(nums[2 * i], nums[2 * i + 1]);
            }
        }
    }
    return nums[0];
}
[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var minMaxGame = function(nums) {
    let n = nums.length;
    while (n !== 1) {
        const m = Math.floor(n / 2);
        for (let i = 0; i < m; i++) {
            if (i % 2 === 0) {
                nums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
            } else {
                nums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
            }
        }
        n = m;
    }
    return nums[0];
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func minMaxGame(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    newNums := make([]int, n/2)
    for i := 0; i < n/2; i++ {
        if i%2 == 0 {
            newNums[i] = min(nums[i*2], nums[i*2+1])
        } else {
            newNums[i] = max(nums[i*2], nums[i*2+1])
        }
    }
    return minMaxGame(newNums)
}

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

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

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。第一次循环的时间复杂度为 O(n)，下一次循环时问题规模减半，所以总体复杂度为 O(n) + O(\dfrac{n}{2}) + O(\dfrac{n}{4}) + \cdots + O(1) = O(n)。

  • 空间复杂度：O(1)。

 Comments
On this page
2293-极大极小游戏