2357-使数组中所有元素都等于零

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

给你一个非负整数数组 nums 。在一步操作中，你必须：

  • 选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
  • nums 中的每个正整数都减去 x。

返回使 nums 中所有元素都等于 __0 需要的 最少 操作数。

示例 1：

**输入：** nums = [1,5,0,3,5]
**输出：** 3
**解释：**
第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。

示例 2：

**输入：** nums = [0]
**输出：** 0
**解释：** nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

方法一：排序 + 模拟

这道题要求计算将非负整数数组 nums 中的所有元素减少到 0 的最少操作数。用 m 表示数组 nums 中的最小非零元素，则可以选择不超过 m 的正整数 x，将数组中的每个非零元素减 x。为了使操作数最少，应选择 x = m，理由如下。

  • 当选择 x = m 时，经过一次操作之后，数组中的所有元素 m 都变成 0，且其余的所有非零元素都减少 m。

  • 当选择 x < m 时，经过一次操作之后，数组中的所有元素 m 在减少 x 之后仍大于 0，为了使数组中的最小非零元素变成 0，至少还需要一次操作，因此至少需要两次操作使数组中的所有元素 m 都变成 0，且其余的所有非零元素都减少 m。

由于当 x < m 时使元素 m 变成 0 的操作数大于当 x = m 时使元素 m 变成 0 的操作数，且两种方案中，使元素 m 变成 0 之后，剩余的最小非零元素相同（所有非零元素都减少 m），因此只有当 x = m 时才能使操作数最少。

根据上述分析，应使用贪心策略使操作数最少，贪心策略为每次选择数组中的最小非零元素作为 x，将数组中的每个非零元素减 x。

可以根据贪心策略模拟操作过程，计算最少操作数。

首先将数组 nums 按升序排序，然后从左到右遍历排序后的数组 nums。对于每个遍历到的非零元素，该元素是数组中的最小非零元素，将该元素记为 x，将数组中的每个非零元素都减 x，将操作数加 1。遍历结束之后，即可得到最少操作数。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minimumOperations(int[] nums) {
        int ans = 0;
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                subtract(nums, nums[i], i);
                ans++;
            }
        }
        return ans;
    }

    public void subtract(int[] nums, int x, int startIndex) {
        int length = nums.length;
        for (int i = startIndex; i < length; i++) {
            nums[i] -= x;
        }
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int MinimumOperations(int[] nums) {
        int ans = 0;
        Array.Sort(nums);
        int length = nums.Length;
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                Subtract(nums, nums[i], i);
                ans++;
            }
        }
        return ans;
    }

    public void Subtract(int[] nums, int x, int startIndex) {
        int length = nums.Length;
        for (int i = startIndex; i < length; i++) {
            nums[i] -= x;
        }
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void subtract(vector<int>& nums, int x, int startIndex) {
        int length = nums.size();
        for (int i = startIndex; i < length; i++) {
            nums[i] -= x;
        }
    }

    int minimumOperations(vector<int>& nums) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            if (nums[i] > 0) {
                subtract(nums, nums[i], i);
                ans++;
            }
        }
        return ans;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static int cmp(const void *pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

void subtract(int* nums, int numsSize, int x, int startIndex) {
    for (int i = startIndex; i < numsSize; i++) {
        nums[i] -= x;
    }
}

int minimumOperations(int* nums, int numsSize) {
    int ans = 0;
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            subtract(nums, numsSize, nums[i], i);
            ans++;
        }
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var minimumOperations = function(nums) {
    let ans = 0;
    nums.sort((a, b) => a - b);
    const length = nums.length;
    for (let i = 0; i < length; i++) {
        if (nums[i] > 0) {
            subtract(nums, nums[i], i);
            ans++;
        }
    }
    return ans;
}

const subtract = (nums, x, startIndex) => {
    const length = nums.length;
    for (let i = startIndex; i < length; i++) {
        nums[i] -= x;
    }
};

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。排序需要 O(n \log n) 的时间，排序之后需要遍历数组一次，对于每个非零元素，将数组中的所有非零元素减去最小非零元素需要 O(n) 的时间，因此时间复杂度是 O(n^2)。

  • 空间复杂度：O(\log n)，其中 n 是数组 nums 的长度。排序需要 O(\log n) 的递归调用栈空间。

方法二：哈希集合

由于每次操作都将数组中的所有非零元素减少一个相同的值，因此数组中的相等元素减少到 0 的操作数相等，数组中的不相等元素减少到 0 的操作数不相等。

又由于使用贪心策略操作时，每次操作都会将数组中的最小非零元素减少到 0，因此最少操作数等于数组中的不同非零元素的个数。

使用哈希集合存储数组中的所有非零元素，则哈希集合的大小等于数组中的不同非零元素的个数，即为最少操作数。

需要注意的是，由于目标是将数组中的所有元素减为 0，如果数组中的一个元素已经是 0 则不需要对该元素执行操作，因此只需要考虑数组中的不同非零元素的个数。

[sol2-Python3]
1
2
3
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        return len(set(nums) - {0})
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int minimumOperations(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if (num > 0) {
                set.add(num);
            }
        }
        return set.size();
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int MinimumOperations(int[] nums) {
        ISet<int> set = new HashSet<int>();
        foreach (int num in nums) {
            if (num > 0) {
                set.Add(num);
            }
        }
        return set.Count;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        unordered_set<int> hashSet;
        for (int num : nums) {
            if (num > 0) {
                hashSet.emplace(num);
            }
        }
        return hashSet.size();
    }
};
[sol2-C]
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
30
31
32
33
34
35
36
37
38
39
40
typedef struct {
    int key;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);             
    }
}

int minimumOperations(int* nums, int numsSize) {
    HashItem *set = NULL;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            hashAddItem(&set, nums[i]);
        }
    }
    int ret = HASH_COUNT(set);
    hashFree(&set);
    return ret;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
var minimumOperations = function(nums) {
    const set = new Set();
    for (const num of nums) {
        if (num > 0) {
            set.add(num);
        }
    }
    return set.size;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
func minimumOperations(nums []int) int {
	set := map[int]struct{}{}
	for _, x := range nums {
		if x > 0 {
			set[x] = struct{}{}
		}
	}
	return len(set)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历数组一次，每个非零元素加入哈希集合的时间是 O(1)。

  • 空间复杂度：O(n)，其中 n 是数组 nums 的长度。哈希集合需要 O(n) 的空间。

 Comments
On this page
2357-使数组中所有元素都等于零