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;
}
相关文章
- 输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的
- 【C/C++学院】0907-象棋五子棋代码分析/寻找算法以及排序算法
- 算法系列15天速成——第三天 七大经典排序【下】
- Linux排序不准确的问题,用以下两行代码解决
- C/C++基础讲解(十二)之数据结构篇排序大舞台
- Linux C 单链表 读取文件 并排序 实例并解释
- C# 选择排序
- ZZNUOJ_C语言1022:三整数排序(完整代码)
- ZZNUOJ_用C语言编写程序实现1183:平面点排序(一)(结构体专题)(附完整源码)
- 基于MPS算法和改进的非支配排序遗传算法II(MNSGA-II)求解配备起重机的模糊鲁棒设施布局问题(Matlab代码实现)
- 【图像处理】基于图像聚类的无监督图像排序问题(Matlab代码实现)
- 1122. 数组的相对排序-力扣双百代码
- 合并两个排序的链表
- 排序(6)---------归并排序(C语言实现)
- go语言笔记——map map 默认是无序的,不管是按照 key 还是按照 value 默认都不排序
- 04、算法系类,快速排序代码实现 + 讲解
- C语言顺序表,合并并排序(代码注释讲解)