2293. Min Max Game
Description
You are given a 0-indexed integer array nums
whose length is a power of 2
.
Apply the following algorithm on nums
:
- Let
n
be the length ofnums
. Ifn == 1
, end the process. Otherwise, create a new 0-indexed integer arraynewNums
of lengthn / 2
. - For every even index
i
where0 <= i < n / 2
, assign the value ofnewNums[i]
asmin(nums[2 * i], nums[2 * i + 1])
. - For every odd index
i
where0 <= i < n / 2
, assign the value ofnewNums[i]
asmax(nums[2 * i], nums[2 * i + 1])
. - Replace the array
nums
withnewNums
. - Repeat the entire process starting from step 1.
Return the last number that remains in nums
after applying the algorithm.
Example 1:
Input: nums = [1,3,5,2,4,8,2,2] Output: 1 Explanation: The following arrays are the results of applying the algorithm repeatedly. First: nums = [1,5,4,2] Second: nums = [1,4] Third: nums = [1] 1 is the last remaining number, so we return 1.
Example 2:
Input: nums = [3] Output: 3 Explanation: 3 is already the last remaining number, so we return 3.
Constraints:
1 <= nums.length <= 1024
1 <= nums[i] <= 109
nums.length
is a power of2
.
Solutions
Solution 1: Simulation
According to the problem statement, we can simulate the entire process, and the remaining number will be the answer. In implementation, we do not need to create an additional array; we can directly operate on the original array.
The time complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|