2208.将数组和减半的最少操作次数

链接：2208.将数组和减半的最少操作次数
难度：Medium
标签：贪心、数组、堆（优先队列）
简介：给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

题解 1 - cpp

• 编辑时间：2023-07-27
• 执行用时：8ms
• 内存消耗：9.3MB
• 编程语言：cpp
• 解法介绍：排序后遍历。

class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), res = 0;
        for (auto &row : grid) sort(row.begin(), row.end());
        for (int j = m - 1; j >= 0; j--) {
            int cur = INT_MIN;
            for (int i = 0; i < n; i++) {
                cur = max(cur, grid[i][j]);
            }
            res += cur;
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-07-27
• 执行用时：112ms
• 内存消耗：16.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def deleteGreatestValue(self, grid: List[List[int]]) -> int:
        for row in grid:
            row.sort()
        n = len(grid)
        m = len(grid[0])
        res = 0
        for j in range(m):
            num = -inf
            for i in range(n):
                num = max(num, grid[i][j])
            res += num
        return res
            

题解 3 - rust

• 编辑时间：2023-07-27
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn delete_greatest_value(mut grid: Vec<Vec<i32>>) -> i32 {
        for row in &mut grid {
            row.sort();
        }
        let mut res = 0;
        for j in 0..grid[0].len() {
            let mut num = i32::MIN;
            for i in 0..grid.len() {
                num = num.max(grid[i][j]);
            }
            res += num;
        }
        res
    }
}