Programming Questions

  • Newest
  • Popular Tags
  • Ask 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
  • -
  • You can do it in expected linear time, using Quickselect: en.wikipedia.org/wiki/Quickselect
  • +
  • 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; }
  • +
  • 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
  • +
  • 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.
    Log in to write an answer.