CODEWITHSUNDEEP
c++algorithm
Chiku
Chiku

Reputation: 21

Find the kth smallest element in an unsorted array of non-negative integers

Not allowed to modify the array ( The array is read only ). Using constant extra space is allowed.

ex: A : [2 1 4 3 2] k : 3

answer : 2

I did it below way. The answer is correct but need to be more memory efficient. 

void insert_sorted(vector<int> &B, int a,int k)
{
    for(int i=0;i<k;i++)
    {
        if(B[i]>=a)
        {
            for(int j=k-1;j>i;j--)
                B[j]=B[j-1];
            B[i]=a;
            return;
        }
    }
}

int Solution::kthsmallest(const vector<int> &A, int k) {

    vector <int> B;
    for(int i=0;i<k;i++)
    {
        B.push_back(INT_MAX);
    }
    int l=A.size();

    for(int i=0;i<l;i++)
    {
        if(B[k-1]>=A[i])
            insert_sorted(B,A[i],k);
    }

    return B[k-1];
}

Upvotes: 1

Views: 2378

Answers (3)

Petar Petrovic
Petar Petrovic

Reputation: 414

One possible solution is binary search.

Let A be the input array; we want to find a number b such that exactly k items in A are smaller than b.

Obviously, b must be inside the range [0, max(A)]. And we do binary search starting with this range.

Suppose we are searching within range [lo, hi]. Let c = (lo + hi)/2 which is the middle pivot. There are three cases:

  • number of items in A less than c are less than k. In this case the number we search for should be larger than c, so it should be in range (c, hi]

  • number of items in A less than c are larger than k. Similarly, the number we search for is in range [lo, c)

  • number of items in A less than c equals to k. In this case, the answer is the minimum element in A that is greater than or equals to c. This can be find by doing a linear search in A again

The complexity is O(n log m), where m is the max element in A.

/* assume k is 0 based, i.e. 0 <= k < n */
int kth_element(const vector<int> &A, int k){
    int lo = 0, hi = *max_element(A.begin(), A.end());
    while (lo <= hi){
        int mid = (lo + hi) / 2;
        int rank_lo = count_if(A.begin(), A.end(), [=](int i){ return i < mid;}); 
        int rank_hi = count_if(A.begin(), A.end(), [=](int i){ return i <= mid;});

        if (rank_lo <= k && k < rank_hi)
            return mid;

        if (k >= rank_hi)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
}

Although it's not the answer to this particular problem (as it requires a modifiable collection), there is a function called std::nth_element, which rearranges the elements so that the kth element is at position k, and all elements at positions less than k are smaller than or equal to the kth element, where k is a input parameter.

Upvotes: 3

DAle
DAle

Reputation: 9117

If only constant extra space is allowed, we can use a simple O(n*k) algorithm.

int kth_smallest(const vector<int>& v, int k) {
    int curmin = -1;
    int order = -1;
    while (order < k) { // while kth element wasn't reached
        curmin = *min_element(v.begin(), v.end(), [curmin](int a, int b) {
            if (a <= curmin) return false; 
            if (b <= curmin) return true;
            return a < b;
        }); // find minimal number among not counted yet

        order += count(v.begin(), v.end(), curmin); // count all 'minimal' numbers
    }
    return curmin;
}

online version to play with: http://ideone.com/KNMYxA

Upvotes: 1

amit
amit

Reputation: 178431

The question does not ask for any time constraints. An O(nk) solution is fairly simple, by iterating the array k times (at most), and discarding one element (and its duplicates) each time.

int FindKthSmallesr(const std::vector<int>& v, int k) {
  // assuming INT_MIN cannot be a value. Could be relaxed by an extra iteration.
  int last_min = INT_MIN;
  while (k > 0) {
    int current_min = INT_MAX;
    for (int x : v) {
      if (x <= last_min) continue;
      current_min = std::min(current_min, x);
    }
    last_min = current_min;
    for (int x : v) {
      if (x == current_min) k--;
    }
  }
  return last_min;
}

Code on ideone: http://ideone.com/RjRIkM

Upvotes: 1

Related Questions