每周一道算法题(十一)
2017-05-27 本文已影响539人
CrazySteven
本周的算法题难度级别Medium,但我用了两天闲散的时间也没通过,最后卡在了“超时”上，上网查了查，不得不钦佩大牛的想法果然牛逼，值得借鉴学习啊
题目:已知一个有n个整数的数组S，找到所有和为0的三个数。（不允许输出重复的解）
说下我的思路，暴力破解，把所有的组合一个一个找，找出复合要求的三个数记录，然后删除重复的，最后剩下的就是答案，需要注意的一个问题就是关于内存的，代码的注释我会写的详细一些，把我遇到的坑都列出来，避免重复踩坑，还要说的一点是这个代码并没有通过全部测试，再倒数第二组的时候就超时了，把样本考出来，在Xcode上运行没有问题，样本有3000个数，大概有1W多个符合要求的集合，在网上运行算法的时候大概找出约3000个集合就超时了，很无奈，如下图：
结果
接下来看看代码：
/**
* Return an array of arrays of size *returnSize.将长度返回给returnSize
* Note: The returned array must be malloced, assume caller calls free().返回的数组需要自己开辟内存空间，不需要考虑释放问题
*/
int** threeSum(int* nums, int numsSize, int* returnSize) {
//由于找不到好的容器，我就用链表了，也算复习一下
struct Node {
int data[3];
struct Node *next;
}node;
int i,j,k;
struct Node *head, *p, *pt;
int len = 0;
head = (struct Node *)malloc(sizeof(node));
head->next = NULL;
p = head;
//将其所有的组合一个一个列举出来，找出符合要求的所有的组合
for (i = 0; i < numsSize; i++) {
for (j = i+1; j < numsSize; j++) {
if (j == i) continue;
for (k = j+1; k < numsSize; k++) {
if (k == i || k == j) continue;
if (nums[i] + nums[j] + nums[k] == 0) {
int x1 = nums[i],x2 = nums[j],x3 = nums[k],t;
//将找出的组合进行排序
if(x1>x2) {t=x1;x1=x2;x2=t;}
if(x2>x3) {t=x2;x2=x3;x3=t;}
if(x1>x2) {t=x1;x1=x2;x2=t;}
//记录长度
len++;
//将排序好的组合通过链表记录
pt = (struct Node *)malloc(sizeof(node));
pt->data[0] = x1;
pt->data[1] = x2;
pt->data[2] = x3;
pt->next = NULL;
p->next = pt;
p = pt;
}
}
}
}
//删除重复的组合
p = head->next;
struct Node *pre;
while(p != NULL) {
pre = p;
while(pre->next != NULL) {
if(pre->next->data[0] == p->data[0] && pre->next->data[1] == p->data[1] && pre->next->data[2] == p->data[2]) {
pt = pre->next;
pre->next = pt->next;
free(pt);
len--;//记录长度
}else pre = pre->next;
}
p = p->next;
}
//返回长度
*returnSize = len;
//将最后的结果整理返回
p = head->next;
//开辟一个二维指针，由于是指针，所有sizeof里面是int*而不是int，写int会提示对齐问题而报错
int **returnPtr = malloc(sizeof(int*) *len);
int x = 0;
while (p != NULL) {
int *arr = malloc(sizeof(int) *3);
for (i = 0;i < 3;i++)
arr[i] = p->data[i];
returnPtr[x++] = arr;
p = p->next;
}
return returnPtr;
}
好遗憾因为超时没过，看了网上的思路，不禁拍手叫绝啊
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void quickSort(int* nums,int first,int end){
int temp,l,r;
if(first>=end)return;
temp=nums[first];
l=first;r=end;
while(l<r){
while(l<r && nums[r]>=temp)r--;
if(l<r)nums[l]=nums[r];
while(l<r && nums[l]<=temp)l++;
if(l<r)nums[r]=nums[l];
}
nums[l]=temp;
quickSort(nums,first,l-1);
quickSort(nums,l+1,end);
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
int i,sum,top=-1,begin,end;
int** res=(int**)malloc(sizeof(int*)*(numsSize*(numsSize-1)*(numsSize-2))/6);
if(numsSize<3){
*returnSize=0;
return res;
}
//将nums从小到大进行排序
quickSort(nums,0,numsSize-1);
for(i=0;i<numsSize;i++){
//从左到右(从小到大)取出一个负数
if(nums[i]>0)break;
if(i>0 && nums[i]==nums[i-1])continue;
//分别找出比这个负数大的最大的数end和最小的数begin
begin=i+1;end=numsSize-1;
//最小的数begin比最大的数小end
while(begin<end){
sum=nums[i]+nums[begin]+nums[end];
if(sum==0){
//记录长度
top++;
res[top]=(int*)malloc(sizeof(int)*3);
res[top][0]=nums[i];res[top][1]=nums[begin];res[top][2]=nums[end];
begin++;end--;
while(begin<end && nums[begin]==nums[begin-1])begin++;
while(begin<end && nums[end]==nums[end+1])end--;
}else if(sum>0) end--;//如果和大于0，则将最大的数缩小
else begin++;//如果和小于0，则将最小的数扩大
}
}
*returnSize=top+1;
return res;
}
概括一下就是先将样本数组从小到大排序，然后遍历找出符合要求的集合进行返回即可，因为进行了排序呢，所以避免了重复的问题，也通过正负数才能得出0的条件进行了剪枝，大大提高了效率，通过各语言的对比，C语言的效率还是遥遥领先，就是感觉不方便。。。
