LeetCode 2363.合并相似的物品

比眉伴天荒 2023-09-26 18:16 126阅读 0赞

### 题目 ###

> 给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质：  
> **items\[i\] = \[valuei, weighti\] 其中 valuei 表示第 i 件物品的 价值 ，weighti 表示第 i 件物品的 重量 。** items 中每件物品的价值都是 唯一的 。 请你返回一个二维数组 ret，其中 **ret\[i\] =  
> \[valuei, weighti\]， weighti 是所有价值为 valuei 物品的 重量之和 。** 注意：ret 应该按价值 升序  
> 排序后返回。

![在这里插入图片描述][1585ba346eaf4c11b7edb2ff49bbbda4.png]

> 二月末的每日一题

思路：这道题的难点在于如何获取两个 items 数组中相同价值的重量之和，并将结果按价值大小进行排序后返回。  
先看一下题目给定输入数据的范围  
![在这里插入图片描述][86785308723d4f3f861382915cc20af6.png]  
由上述的信息，可以得出 **两个items 数组中 val与weight 的取值范围是大于等于1并小于等于1000的**，那么就可以利用哈希表的思路，来求得 items 数组中相同价值的总重量。

由于数据范围仅仅在 \[1~1000\]，这个闭区间之内，所以我们可以用哈希数组来代替哈希表，能够提高效率，**使用 items\[i\]\[0\] 数组中的价值为哈希数组下标，将相同的价值的重量累加起来。**

### 代码 ###

//二维数组排序函数
    int cmp(const void *pa, const void *pb) {
        
        int *a = *(int **)pa;
        int *b = *(int **)pb;
        return a[0] - b[0];
    }
    /**
     * Return an array of arrays of size *returnSize.
     * The sizes of the arrays are returned as *returnColumnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
     /*
     题目给定的函数格式 
    	 items为二维数组
    	 itemsSize是传入二维数组长度
    	 items1ColSize是二维数组子数组的长度
    	 returnSize是一级指针，需要赋值为返回的结果数组的长度
    	 returnColumnSizes是二级指针，需要赋值为结果数组子数组的长度。
     */
    int** mergeSimilarItems(int** items1, int items1Size, int* items1ColSize, int** items2, int items2Size, int* items2ColSize, int* returnSize, int** returnColumnSizes)
    {
        
        int hash[1001]={
        0};	//hash数组
    
        //将数组1的重量以价值为下标存放在hash数组中
        for(int i=0; i<items1Size; ++i)
        {
        
            hash[items1[i][0]]=items1[i][1];
        }
        //将数组2的重量以价值为下标并加上相同价值的重量存放在hash数组中
        for(int i=0; i<items2Size; ++i)
        {
        
            hash[items2[i][0]]+=items2[i][1];
        }
        
        //最坏情况下需要存储两个数组的所有数据。
        int **res=(int **)malloc(sizeof(int *)*(items1Size+items2Size));
        *returnSize=0;  //存储长度的指针初始为零
    
        for(int i=0; i<items1Size; ++i)
        {
           
            //如果hash数组中的值不为零，那么说明该值还没有被存储过，所以将该值存储下来
            if(hash[items1[i][0]] != 0)
            {
        
                res[*returnSize]=(int *)malloc(sizeof(int)*(2));
                res[*returnSize][0]=items1[i][0];
                res[*returnSize][1]=hash[items1[i][0]];
                hash[items1[i][0]]=0;   //赋值为零，防止重复进入
                ++(*returnSize);
            }
        }
        //该循环作用与上述循环相同
        for(int i=0; i<items2Size; ++i)
        {
           
            if(hash[items2[i][0]] != 0)
            {
        
                res[*returnSize]=(int *)malloc(sizeof(int)*(2));
                res[*returnSize][0]=items2[i][0];
                res[*returnSize][1]=hash[items2[i][0]];
                hash[items2[i][0]]=0;   //赋值为零，防止重复进入
                ++(*returnSize);
            }
        }
        //为返回数组的子数组长度赋值
        *returnColumnSizes=(int *)malloc(sizeof(int)*(*returnSize));
        for(int i=0; i<*returnSize; ++i)
        {
        
            (*returnColumnSizes)[i]=2;
        }
        //将结果数组排序以价值排序
        qsort(res,(*returnSize),sizeof(int *),cmp);
        //返回
        return res;
    }

### 结果 ###

![在这里插入图片描述][840c5fc7fb4741459a3a612a16158142.png]

### 结尾 ###

二月再见，三月你好。  
如果各位有更优解的话，可发布在评论区，相互进步。

[1585ba346eaf4c11b7edb2ff49bbbda4.png]: https://img-blog.csdnimg.cn/1585ba346eaf4c11b7edb2ff49bbbda4.png
[86785308723d4f3f861382915cc20af6.png]: https://img-blog.csdnimg.cn/86785308723d4f3f861382915cc20af6.png
[840c5fc7fb4741459a3a612a16158142.png]: https://img-blog.csdnimg.cn/840c5fc7fb4741459a3a612a16158142.png