Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Find a lost number in O(N) better than O(NlogN) by sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
double print_time(struct timeval *s, struct timeval *e){
int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000;
int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000;
return (double)(ei-si)/1000.0;
}
int compare_int(const void *a, const void*b){
return *(int*)a-*(int*)b;
}
void debug(int c, int* data){
if(c>100) return;
int i;
for(i=0;i<c;i++){
printf("%d,",data[i]);
}
printf("\n");
}
int find(int num, int low, int high,int* data){
//debug(num,data);
int mid = low+(high-low)/2;
if(num==0) return mid;
if(num==1){
if(*data==mid) return high;
else return mid;
}
int* below = malloc(sizeof(int)*(num/2+1));
int* above = malloc(sizeof(int)*(num/2+1));
int cb = 0;
int ca = 0;
int i;
//printf("low,mid,high = %d,%d,%d\n",low,mid,high);
for(i=0;i<num;i++){
if(data[i]<mid){
below[cb++]=data[i];
}else{
above[ca++]=data[i];
}
}
if(cb<(mid-low)){
return find(cb,low,mid-1,below);
}else{
return find(ca,mid,high,above);
}
}
void scramble(int c, int* data){
srand((unsigned)time(NULL));
int i,m,n,t;
m = 0;
// Scramble twice longer than the size
for(i=0;i<c*2;i++){
t = data[m];
n = rand()%c;
data[m] = data[n];
data[n] = t;
m = n;
}
}
void func_O_N(int c, int* data){
int deleted = data[c-1];
int found = find(c-1,1,c,data);
printf("%d==%d:%s\n",deleted,found,deleted==found?"OK":"NG");
}
void func_O_NlogN(int c, int* data){
int deleted = data[c-1];
int found = 0;
qsort(data,c-1,sizeof(int),compare_int);
int i;
for(i=0;i<c-1;i++){
if(data[i]!=i+1){
found = i+1;
break;
}
}
if(found==0) found=c;
printf("%d==%d:%s\n",deleted,found,deleted==found?"OK":"NG");
}
int main(int argc, char* argv[]){
if(argc!=2) exit(1);
int c = atoi(argv[1]);
int* data = malloc(sizeof(int)*c);
int i;
for(i=0;i<c;i++){
//*data++ = i;
data[i] = i+1;
}
scramble(c,data);
struct timeval s, e;
gettimeofday(&s,NULL);
func_O_N(c,data);
gettimeofday(&e,NULL);
printf("func_O_N : %.2lf sec.\n",print_time(&s,&e));
gettimeofday(&s,NULL);
func_O_NlogN(c,data);
gettimeofday(&e,NULL);
printf("func_O_NlogN : %.2lf sec.\n",print_time(&s,&e));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment