Programming Questions

  • Newest
  • Popular Tags
  • Ask A Question
  • Nth Smallest Number
    Find the nth smallest number in an unsorted array of numbers. Do it in linear time and without using any added memory. I can do it using array but I don't know how to do it without using more memory.
    ikonijab posted this question on 2/6/14 | java
    Answers
  • +
  • 1
  • -
  • There is a built-in STL function for that in C++, it does use memory but afaik not from the heap, which is what I think the intended meaning was.
    #include <iostream>
    #include <cstdlib>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    int main(int argc, char **argv) {
    	int nth=0;
    	vector<unsigned short> the_array;
    	the_array.push_back(14103);
    	the_array.push_back(16942);
    	the_array.push_back(32741);
    	the_array.push_back(24092);
    	the_array.push_back(11611);
    	the_array.push_back(456);
    	the_array.push_back(13360);
    	the_array.push_back(27782);
    	the_array.push_back(2860);
    	the_array.push_back(25439);
    	if(argc==2) {
    		nth=atoi(argv[1])-1;
    		if(nth<0 || nth>=the_array.size()) {
    			cerr<<"Argument out of range, please specify an argument between 1 and "<<the_array.size()<<" inclusive."<<endl;
    			return 1;
    		}
    	}
    	nth_element(the_array.begin(),the_array.begin()+nth,the_array.end(),less<unsigned short>());
    	nth++;
    	cout<<"The "<<nth<<((nth==1)?"st":(nth==2)?"nd":(nth==3)?"rd":"th")<<" smallest is "<<the_array[nth-1]<<'.'<<endl;
    	return 0;
    }
    
  • +
  • 1
  • -
  • You can do it in expected linear time, using Quickselect: en.wikipedia.org/wiki/Quickselect
  • +
  • 0
  • -
  • If you could find a way to find the nth smallest number in linear time, you could make quick sort worst case O(n*log(n)). I don't believe anyone knows how to do that.
  • +
  • 0
  • -
  • Is there a limiation of not changing the argument array? if not sort on the same array and return the length - n entry in the sorted array
    Log in to write an answer.