Leetcode-2293 Min Max Game

题目

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

1. Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.
2. For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
3. For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
4. Replace the array nums with newNums.
5. Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

题目解析

实际上就是一个非常简单的取最大值最小值的问题，有两种解法：递归和循环。

循环：

因为之后也不会再用到 nums[i]这个数字，在进行计算了之后，并不会再次被用到，所以可以原地修改，节省空间。

时间复杂度：O(n)

空间复杂度：O(1)

func minMaxGame(nums []int) int {
    length := len(nums)
	for length > 1 {
		length = length / 2
		for i := 0; i < length; 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]
}

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

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

递归：

在计算出新的数组之后，传入func，当n==1的时候返回nums[0]，其余就递归就行

func minMaxGame(nums []int) int {
    length := len(nums)
	if length == 1{
		return nums[0]
	}
	newNums := make([]int, length / 2)
	for i := 0; i < length / 2; 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)
}

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

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