LeetCode·304竞赛·6132·使数组中所有元素都等于零·模拟·哈希

链接：https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/solution/by-xun-ge-v-a5s6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路

• 暴力求解

题目需要我们寻找 最少 操作数，那么直接按题目给定要求进行模拟操作：

• 对元素进行升序处理，每次寻找第一个非0元素 x
• 选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
• nums 中的每个正整数都减去 x。
• 减去会再升序处理

• 简易哈希表

再次读题目，可以发现，其实题目就等价于求数组中非0元素的个数，我们定义一个简易哈希表记录数组中不同元素的个数，最后相加即可

代码

暴力求解

int cmp(const void * a, const void * b)//升序
{
    return *(int *)a - *(int *)b;
}
int minimumOperations(int* nums, int numsSize){
    qsort(nums, numsSize,sizeof(int), cmp);//升序
    int conut = 0;
    for(int i = 0; i < numsSize; i++)//枚举整个数组
    {
        if(nums[i] == 0)//寻找第一个非0元素
        {
            continue;
        }
        conut++;
        int m = nums[i];
        for(int j = i; j < numsSize; j++)//nums 中的每个正整数都减去 x
        {
            nums[j] = nums[j] - m;
        }
        qsort(nums, numsSize,sizeof(int), cmp);//再升序
    }
    return conut;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/solution/by-xun-ge-v-a5s6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

简易哈希表

int minimumOperations(int* nums, int numsSize){
    int ans[101];
    memset(ans, 0, sizeof(int) * 101);//初始化
    for(int i = 0; i < numsSize; i++)//记录不同元素的个数
    {
        ans[nums[i]] = 1;
    }
    int conut = 0;
    for(int i = 1; i < 101; i++)//累加
    {
        conut += ans[i];
    }
    return conut;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/solution/by-xun-ge-v-a5s6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度