15. 三数:和-c语言-极快排序+哈希表+二分查找
15. 三数之和-c语言-快速排序 哈希表 二分查找
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] nums[j] nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] nums[1] nums[2] = (-1) 0 1 = 0 。
nums[1] nums[2] nums[4] = 0 1 (-1) = 0 。
nums[0] nums[3] nums[4] = (-1) 2 (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 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().
*/
void quick_sort(int *a,int low,int high){
int l=low,h=high;
if(low<high){
int p=a[low];
while(low<high){
while(low<high&&a[high]>=p){
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=p){
low ;
}
a[high]=a[low];
}
a[low]=p;
quick_sort(a,l,low-1);
quick_sort(a,low 1,h);
}
}
#define size 10000
struct hash{
struct hash *next;
int val;
int index;
};
void add_hash(struct hash* h,int val,int index){
struct hash*p=(struct hash *)malloc(sizeof(struct hash ));
p->index=index;
p->val=val;
p->next=h->next;
h->next=p;
}
bool find(struct hash *h,int val,int index1,int index2){
struct hash*p=h->next;
while(p){
if(p->val==val&&index1!=p->index&&index2!=p->index){
return true;
}
p=p->next;
}
return false;
}
bool find2(struct hash *h,int val){
struct hash*p=h->next;
while(p){
if(p->val==val){
return true;
}
p=p->next;
}
return false;
}
int find_b(int* nums,int numsSize,int val){
int low=0;
int high=numsSize-1;
while(low<=high){
int mid=(low high)/2;
if(nums[mid]>=val){
high=mid-1;
}
else{
low=mid 1;
}
}
return high;
}
int cmp(const void* a, const void* b)
{
return *(int*)a - *(int*)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
quick_sort(nums,0,numsSize-1);
int p=numsSize*10;
int sizet=0;
int **re=(int** )malloc(sizeof(int*)*p);
if(nums[0]>0||nums[numsSize-1]<0){
*returnSize=sizet;
return re;
}
* returnColumnSizes=(int* )malloc(sizeof(int)*p);
for(int i=0;i<p;i ){
re[i]=(int* )malloc(sizeof(int*)*3);
(* returnColumnSizes)[i]=3;
}
struct hash *h=(struct hash *)malloc(sizeof(struct hash )*size);
for(int i=0;i<size;i ){
(h i)->next=NULL;
}
struct hash *ht=(struct hash *)malloc(sizeof(struct hash )*size);
for(int i=0;i<size;i ){
(ht i)->next=NULL;
}
for(int i=0;i<numsSize;i ){
if(nums[i]>=0)
add_hash(h abs(nums[i])%size,nums[i],i);
}
int pre=nums[0] 1;
for(int i=0;i<numsSize;i ){
if(nums[i]!=pre){
if(i 1==numsSize){
continue;
}
int pret=nums[i 1] 1;
int index=find_b(nums,numsSize,-nums[i]-nums[numsSize-1]);
// printf("%d %d|| ",index,nums[i]);
index=fmax(index,i 1);
int j;
for( j=index;j<numsSize; j ){
if(nums[j]!=pret){
if(nums[j] nums[i]<=0){
if(find2(ht i%size,nums[j])==false){
if(find(h abs(nums[j] nums[i])%size,abs(nums[j] nums[i]),i,j)){
re[sizet][0]=nums[i];
re[sizet][1]=nums[j];
re[sizet][2]=abs(nums[j] nums[i]);
sizet ;
add_hash(ht i%size,nums[j],-1);
add_hash(ht i%size,abs(nums[j] nums[i]),-1);
}
}
}
else{
break;
}
pret=nums[j];
}
}
pre=nums[i];
}
}
*returnSize=sizet;
return re;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgaghhe
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01