Here’s the problem:
————-
Given the list of numbers, you are to sort them in non decreasing order.
Input
t – the number of numbers in list, then t lines follow [t <= 10^6]. Each line contains one integer: N [0 <= N <= 10^6] Output
Output given numbers in non decreasing order.
Example
Input:
5
5
3
6
7
1
Output:
1
3
5
6
7
—————–
As you probably can guess the main challenge here is the speed at which you can process and sort the input. My solution was to simply create an empty array, and increment each position according to the numbers that were given as input. After that I would only need to traverse the array once outputing all the respective numbers. It worked.
#include <stdio.h>
int array[1000001] = {0};
int main(){
int i,j;
scanf("%d",&j);
int x;
for (i=0;i<j;i++){
scanf("%d",&x);
array[x]++;
}
for (i=0;i<1000001;i++){
while(array[i]>0){
printf("%dn",i);
array[i]--;
}
}
return 0;
}
I am not understanding the working of following code:
for (i=0;i<j;i++){
scanf("%d",&x);
array[x]++;
}
will u please explain how array[x]++ is working here.
Oh! i got it
it is just increasing the indices value….
without swapping how did it worked.
and reversing it didn’t get that?
1. Won’t there be garbage values to some values for ‘x’? if the value is not inputted?
2. what if a number occurs twice ?
You’ve got to be kidding me!!! Tried with merge sort quick sort,Java’s inbuilt sort but it didn’t worked!!
Finally solved that too with easiest solution I can think of. Taken only 2.12 secs when the limit is 5 secs
I tried doing the same thing in cpp, but its not working.
#include
using namespace std;
int main(){
int A[1000001]={0};
int n;
cin >> n;
int a;
while(n–){
cin >> a;
A[a]= A[a]+1;
}
int i=0;
while(i0){
cout << i << endl;
A[i]–;
}
i++;
}
return 1;
}
use scanf and printf instead of cin and cout
This code is good for quickly sorting values but this code fails when two or more same elements are entered in the array so don’t rely on this code take use of merge or heap sort