There
is a linked list of numbers of length N. N is very large and you don’t
know N. You have to write a function that will return k random numbers
from the list. Numbers should be completely random.
Conditions :
Conditions :
- Use random number function rand() that returns a number between 0 and 1
- It must be done in O(N) time
Solution :
- Take 2 arrays R[K] and Num[K]
- For each element in sorted array read one by one and do :
- Generate a random number r
- If R is not full, insert r into R and element into Num array else replace r with highest random number in R and insert current element into corresponding index in Num array (Note that we want to keep the least K random numbers and corresponding elements in list)
- Print Num[]
- Time : O(N)
- Space : O(K)
Code :
void random_selection(int[] input, int N, int K){
int number[K];
double random[K];
int count = 0;
for(int i=0; i<N; i++){
double random[K];
int count = 0;
for(int i=0; i<N; i++){
double r = rand();
if(r < number[count-1]){
index = insert(random, K, &count, r);number[index] = input[i];
}
}
for(int i=0; i<K; i++){
}for(int i=0; i<K; i++){
printf("%d ", number[i]);
}int insert(double *list, int K, int *count, double entry){
if(*count == K-1){
int i = *count;
while(*(list+i) > entry){
*(list + i + 1) = entry;
(*count)++;
return i+1;
(*count)--;
}int i = *count;
while(*(list+i) > entry){
*(list + i + 1) = *(list + 1);
i--;
}i--;
*(list + i + 1) = entry;
(*count)++;
return i+1;
}
No comments:
Post a Comment