|
If you don't care about time, sort the whole array and parameter n is virtually useless !
S(a, m);
where S stands for some sorting algorithm on an array.
Slightly shorter in Python, assuming a has length m :
S(a) # Solution in a[0..n-1]
modified 5-Mar-12 3:25am.
|
|
|
|
|
var nSmallestNumbers = numbers.OrderBy(x => x).Take(n);
|
|
|
|
|
maybe in F# (doesn't check if n < X.Length):
let nsmallest X n = (Array.sort X).[0..(n-1)]
|
|
|
|
|
int n = 2;
int[] m = { 3, 5, 7, 1, 8, 4, 2 };
int[] smallest = (int[])Array.CreateInstance(typeof(int), n);
Array.Sort(m); Array.ConstrainedCopy(m, 0, smallest, 0, n);
Kevin Rucker, Application Programmer
QSS Group, Inc.
United States Coast Guard OSC
Kevin.D.Rucker@uscg.mil
"Programming is an art form that fights back." -- Chad Hower
|
|
|
|
|
Hi there, nice challenge !
Didn't want to use language built in array sorting, since that makes the solution obvious.
Ok ok, recursion is dangerous, but looks nice
function reduceTo(arr,n){
if (n==arr.length) return arr;
var next=Array();
for (i=0,max=0; i<arr.length; i++){
if (arr[i]>=arr[max]) {
if (max!=i) next[next.length]=arr[max];
max=i;
}
else{
next[next.length]=arr[i];
}
}
return reduceTo(next,n);
}
|
|
|
|
|
in Java (without dublicates handling)
// given an array of ints: m
// and a number n, for example n =4
// we can use a java.util.TreeSet (that is, ordered set) to do the job:
TreeSet <integer> result = new TreeSet <integer> ();
for (int mcnt=0; mcnt < m.length ; mcnt++)
if (result.size() < n) {
result.add(m[mcnt]);
continue;
} else {
int curMax = result.last();
if (curMax > m[mcnt]) {
result.remove(curMax);
result.add(m[mcnt]);
}
}
|
|
|
|
|
A submission in C:
#include<malloc.h>
int*f(int*s,int m,int n){int i,c,*a=(int*)malloc(n*sizeof(int));for(;n;m--,s++){for(i=1,c=0;i<m;i++)if(s[i]<=*s)c++;if(c<n)a[--n]=*s;}return a;}
Assumptions: the numbers are integers, "smaller" for negative numbers means "more negative", and the initial set of numbers is stored as an array. A different data structure would require reworking the algorithm, but the first two assumptions are easy to change with a few extra bytes-- for instance, for doubles, we can do it as:
#include<malloc.h>
#define D double
D*f(D*s,int m,int n){int i,c;D*a=(D*)malloc(n*sizeof(D));for(;n;m--,s++){for(i=1,c=0;i<m;i++)if(fabs(s[i])<=fabs(*s))c++;if(c<n)a[--n]=*s;}return a;}
and for a "closer to zero" definition of smaller numbers, the integer version would change to:
#include<malloc.h>
#include<math.h>
int*f(int*s,int m,int n){int i,c,*a=(int*)malloc(n*sizeof(int));for(;n;m--,s++){for(i=1,c=0;i<m;i++)if(fabs(s[i])<=fabs(*s))c++;if(c<n)a[--n]=*s;}return a;}
If you test it, don't forget to free() the returned array. And for heaven's sake, don't ever write real code like this (and I don't just mean the formatting).
|
|
|
|
|
If our list is the_list in Python we have
new_list = sorted(the_list)[:n]
|
|
|
|
|
This is a straight selection sort, processing back to front and doing immediate swaps to avoid index bookeeping.
void g(int a[], int m)
{
for (int s, p; p= --m;)
while (p--)
if (s= a[m], a[p] > s)
a[m]= a[p], a[p]= s;
}
or, said shortly,
void g(int*a,int m){for(int s,p;p=--m;)while(p--)if(s=a[m],a[p]>s)a[m]=a[p],a[p]=s;}
The requested solution lies in a[0..n-1] .
I guess it will be hard to improve on this straight selection approach, given that
- two nested loops are required,
- two decreasing indexes are required (m and p ),
- a swap variable is required (s ),
- a key comparison is required,
- three assignments are required for the swaps, wherever they take place.
modified 6-Mar-12 6:44am.
|
|
|
|
|
Actually, we can do away with one of the loops if we make use of some evaluation short circuiting trickery to make one loop act like two. Thus this:
void g(int*a,int m){for(int s,p;p=--m;)while(p--)if(s=a[m],a[p]>s)a[m]=a[p],a[p]=s;}
becomes this:
void g(int*a,int m){for(int s,p=0;p--||(p=--m);)if(s=a[m],a[p]>s)a[m]=a[p],a[p]=s;}
which saves us one whole character. It might be possible to figure out a way to cut off a couple more, I'm not sure. I've considered, but not had enough time to exhaust, possibilities like going forward vs. backward on either one or both of the iterators, using a pointer rather than an index into the array, whether sorting in reverse order (putting the smallest elements at the end of the array rather than the beginning) might help, and the possibility of somehow using the array itself for swapping to eliminate a variable, but probably most of these are going to add code rather than reduce it. There's also the possibility of a recursive solution, but I haven't really tried that at all.
I have to go do some real work, unfortunately, but this C solution is getting surprisingly close in length to some of the solutions using languages with handy built-in functions to do this sort of thing.
|
|
|
|
|
|
Let x be such a sample. Then x[rank(x)<=n] is such a subsample, in R.
If there are elements in the sample that are repeated and you want the first n different numbers, it is a bit more complicated, since you have to check first that there are at least n different elements in your sample, using ux<-unique(x), for instance.
modified 11-Mar-12 11:18am.
|
|
|
|
|
I noticed this morning that a low rep user has gone through and down-voted a bunch of my answers in Q&A this morning. (9 to be exact) All of these were done within 1-2 minutes so it is quite clear that they didn't even read the questions or answers and it was simply a reactionary down-voting spree.
Does this mean that I've arrived as a "real" CP participant?
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
Not until you come over to the brown and crunchy side.
Panic, Chaos, Destruction. My work here is done.
Drink. Get drunk. Fall over - P O'H
OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre
I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer
Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
|
|
|
|
|
Nagy Vilmos wrote: Not until you come over to the brown and crunchy side.
I've loved brown and crunchy[^] my whole life. Does that count?
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
Pass friend.
Panic, Chaos, Destruction. My work here is done.
Drink. Get drunk. Fall over - P O'H
OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre
I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer
Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
|
|
|
|
|
Yup, welcome to the club!
|
|
|
|
|
Your badge, poster, mug, tee shirt and complimentary copy of "What a Wanker!" magazine are on their way to you as you speak.
We all get them, I have regular, but you must always smile and think "What a Wanker!" when you see them do these pathetic little things.
---------------------------------
I will never again mention that I was the poster of the One Millionth Lounge Post, nor that it was complete drivel. Dalek Dave
CCC Link[ ^]
English League Tables - Live
|
|
|
|
|
Dalek Dave wrote: but you must always smile and think "What a Wanker!" when you see them do these pathetic little things.
Then I guess I'm there... That's exactly what I was thinking, including the sarcastic "Oh boy do those -18 total points hurt".
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
There There, have 24 back.
---------------------------------
I will never again mention that I was the poster of the One Millionth Lounge Post, nor that it was complete drivel. Dalek Dave
CCC Link[ ^]
English League Tables - Live
|
|
|
|
|
Got my copy of WAW mag this month. Jim Davison features on the cover.
|
|
|
|
|
I gave you some points to help with the itching and the burning.
|
|
|
|
|
I could care less about the points, that's why I was careful to mention only that I got a "grouping of down-votes". But thanks for the +.
I wasn't, now I am, then I won't be anymore.
|
|
|
|
|
How much less could you care?
Panic, Chaos, Destruction. My work here is done.
Drink. Get drunk. Fall over - P O'H
OK, I will win to day or my name isn't Ethel Crudacre! - DD Ethel Crudacre
I cannot live by bread alone. Bacon and ketchup are needed as well. - Trollslayer
Have a bit more patience with newbies. Of course some of them act dumb - they're often *students*, for heaven's sake - Terry Pratchett
|
|
|
|
|
Perhaps some of could take a wander round his articles and down vote them!
(I won't, but I bet he would care then! )
---------------------------------
I will never again mention that I was the poster of the One Millionth Lounge Post, nor that it was complete drivel. Dalek Dave
CCC Link[ ^]
English League Tables - Live
|
|
|
|
|