217. Contains Duplicate(C语言)

一个数组，如果有重复的数就返回true，都不相同就返回false

好不容易调好了，超时，网上都说用哈希，map什么的，找了半天都是java。。。。

下面是我那个O(n^2)超时的程序，先冒泡升序排序再两两比较

bool containsDuplicate(int* nums, int numsSize) { int flag = 0,temp=0; if(numsSize==1||numsSize==0){ flag=0; }else{ for(int j=0;j<numsSize;j++){ for(int i=0;i<numsSize-1;i++){ if(nums[i]>nums[i+1]){ temp=nums[i+1]; nums[i+1]=nums[i]; nums[i]=temp; } } } for(int i=0;i<numsSize;i++){ if(nums[i]==nums[i+1]){ flag=1; break; } } } return flag; }

柏宁提供了新思路

先遍历一遍，寻找给出数组的最小值和最大值

建立一个新的数组，从最小值到最大值那么长

让给定的数组的值对应到新的数组里

再遍历一遍新的数组，如果〉1说明有重复的，如果都《1，说明没有重复的

bool containsDuplicate(int* nums, int numsSize) { int i=0; int max=0,min=0; int bufsize=0; int *buf; int temp=0; if(numsSize<2){ return false; } max=nums[0]; min=nums[0]; //找最大值和最小值 for(i=0;i<numsSize;i++){ if(nums[i]>max){ max=nums[i]; } if(nums[i]<min){ min=nums[i]; } } //新建数组 bufsize=max-min+1; buf=(int *)malloc(bufsize*sizeof(int)); memset(buf,0,bufsize*sizeof(int)); for(i=0;i<numsSize;i++){ temp=nums[i]-min; if(buf[temp]==0){ buf[temp]=1; }else{ return true;//如果nums[temp]!=0说明已经有一个也就说重复了 } } return false; } memset这里百度了一下

因为我申请的是int，长度是4字节，所以后面要写成bufsize*sizeof(int)或者bufsize*4

伯宁说申请成char类型的数组就行，是1字节，而且后面是下标，值就0，1用不了那么多字节

不管了土豪