1452. 收藏清单-排序+交叠比较-力扣双百代码

1452. 收藏清单-排序+交叠比较-力扣双百代码

给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。

请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。

示例 1：

输入：favoriteCompanies = [[“leetcode”,“google”,“facebook”],[“google”,“microsoft”],[“google”,“facebook”],[“google”],[“amazon”]]
输出：[0,1,4]
解释：
favoriteCompanies[2]=[“google”,“facebook”] 是 favoriteCompanies[0]=[“leetcode”,“google”,“facebook”] 的子集。
favoriteCompanies[3]=[“google”] 是 favoriteCompanies[0]=[“leetcode”,“google”,“facebook”] 和 favoriteCompanies[1]=[“google”,“microsoft”] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。

示例 2：

输入：favoriteCompanies = [[“leetcode”,“google”,“facebook”],[“leetcode”,“amazon”],[“facebook”,“google”]]
输出：[0,1]
解释：favoriteCompanies[2]=[“facebook”,“google”] 是 favoriteCompanies[0]=[“leetcode”,“google”,“facebook”] 的子集，因此，答案为 [0,1] 。

示例 3：

输入：favoriteCompanies = [[“leetcode”],[“google”],[“facebook”],[“amazon”]]
输出：[0,1,2,3]

其实这一题，个人觉得精髓就在于，对数据进行排序后，我们可以对他们进行比较时，进行交叠比较，这样，可以极大降低时间开销，解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 bool include(char **a,int asize,char **b,int bsize){
   
     int i=0,j=0;
     int same=0;

     while(i!=asize&&bsize!=j){
           if(strcmp(a[i],b[j])==0){
               i++;
               j++;
               same++;
           }
           else{
               if(asize==bsize){
                   return false;
               }
               if(asize>bsize){
                   i++;
               }
               else{
                   j++;
               }
           }
         
     }
  
     
     if(same==asize||same==bsize){
         return true;
     }
     return false;
 }



int Comp(const void *a, const void *b)
{
    char *str1 = *(char**)a;
    char *str2 = *(char**)b;
    return strcmp(str1, str2);
}
int* peopleIndexes(char *** favoriteCompanies, int favoriteCompaniesSize, int* favoriteCompaniesColSize, int* returnSize){
    *returnSize = 0;
    if(favoriteCompanies == NULL || favoriteCompaniesSize <= 0 || favoriteCompaniesColSize == NULL) {
        return NULL;
    }
    int* ans = (int*)malloc(favoriteCompaniesSize * sizeof(int));
    memset(ans, 0, favoriteCompaniesSize * sizeof(int));
    for(int i = 0; i < favoriteCompaniesSize; i++) {
        qsort(favoriteCompanies[i], favoriteCompaniesColSize[i], sizeof(char*), Comp);
    }

    int *re=(int *)malloc(sizeof(int)*favoriteCompaniesSize);
    int size=0;
    
    for(int i=0;i<favoriteCompaniesSize;i++){
        re[i]=1;
     
    }

    for(int i=1;i<favoriteCompaniesSize;i++){
        for(int j=0;j<i;j++){
          
            if(re[j]==1&&re[i]==1){

              
            
                 if(include(favoriteCompanies[i],favoriteCompaniesColSize[i],favoriteCompanies[j],  favoriteCompaniesColSize[j])){
                    
                     if(favoriteCompaniesColSize[i]<favoriteCompaniesColSize[j]){
                         re[i]=0;
                     }
                     else{
                         re[j]=0;
                     }
                  
                     if(re[i]==0){
                         break;
                     }

            }

            }
           
        }
    }
   
    for(int i=0;i<favoriteCompaniesSize;i++){
       
        if(re[i]==1){
            re[size++]=i;
        }
    }
    *returnSize=size;
    return re;

}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99