给你一个正整数数组 nums 。每一次操作中你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。注意在后续操作中你可以对减半过的数继续执行操作请你返回将 nums 数组和 至少 减少一半的 最少 操作数。 示例 1：输入：nums = 51981输出：3解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。以下是将数组和减少至少一半的一种方法：选择数字 19 并减小

解法一：排序+贪心算法

思路：

1. 首先对数组进行排序，从大到小；
2. 然后计算数组的总和 sum；
3. 从最大的数开始遍历，每次将当前数减半，直到 sum 的值小于等于 sum/2；
4. 返回遍历的次数。

时间复杂度分析：排序的时间复杂度为 O(nlogn)，遍历整个数组的时间复杂度为 O(n)，所以总的时间复杂度为 O(nlogn)。

class Solution { func halveArray(_ nums: [Int]) -> Int { var sortedNums = nums.sorted(by: >) var sum = sortedNums.reduce(0, +) var count = 0

    for i in 0..<sortedNums.count {
        sum -= sortedNums[i]
        count += 1
        
        if sum <= sortedNums[i] {
            break
        }
    }
    
    return count
}

}

解法二：堆排序

思路：

1. 使用堆排序对数组进行排序，从大到小；
2. 然后计算数组的总和 sum；
3. 从最大的数开始遍历，每次将当前数减半，直到 sum 的值小于等于 sum/2；
4. 返回遍历的次数。

时间复杂度分析：堆排序的时间复杂度为 O(nlogn)，遍历整个数组的时间复杂度为 O(n)，所以总的时间复杂度为 O(nlogn)。

class Solution { func halveArray(_ nums: [Int]) -> Int { var heap = Heap(nums, >) var sum = nums.reduce(0, +) var count = 0

    while sum > heap.peek()! {
        sum -= heap.remove()!
        count += 1
    }
    
    return count
}

}

解法三：动态规划

思路：

1. 首先计算数组的总和 sum；
2. 创建一个二维数组 dp，dp[i][j] 表示在前 i 个数中选择 j 个数使得和最小的情况下，和减少至少一半所需要的最少操作数；
3. 初始化 dp[i][0] = 0，表示在前 i 个数中选择 0 个数，和已经减少至少一半，所以不需要操作；
4. 遍历数组，对于每个数 nums[i]，对于 j 从 1 到 i，计算 dp[i][j]，表示在前 i 个数中选择 j 个数使得和最小的情况下，和减少至少一半所需要的最少操作数；
   • 如果 nums[i] <= dp[i-1][j-1]，那么 dp[i][j] = dp[i-1][j-1]，表示可以直接使用 nums[i] 来减小和；
   • 否则，dp[i][j] = dp[i-1][j-1] + nums[i]，表示需要将 nums[i] 减半，然后再减小和；
5. 返回 dp[nums.count-1][nums.count/2]，即为最少操作数。

时间复杂度分析：遍历整个数组的时间复杂度为 O(n^2)，所以总的时间复杂度为 O(n^2)。

class Solution { func halveArray(_ nums: [Int]) -> Int { var sum = nums.reduce(0, +) var dp = Array(repeating: Array(repeating: Int.max, count: nums.count/2+1), count: nums.count+1)

    for i in 0...nums.count {
        dp[i][0] = 0
    }
    
    for i in 1...nums.count {
        for j in 1...i {
            if nums[i-1] <= dp[i-1][j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = dp[i-1][j-1] + nums[i-1]
            }
        }
    }
    
    return dp[nums.count][nums.count/2]
}