1

This is the same question as An algorithm to find the nth largest number in two arrays of size n EXCEPT that the two sorted arrays are of different sizes.

I tried to implement a version of the algorithm similar to the one suggested to adhere to my problem but I can't show its correctness. It appears to fail for k = 6. The pair being returned are the indices for list1 and list2 respectively when the algorithm finishes.

#include <iostream>
#include <utility>

using namespace std;

pair<int, int> smallestKElements(int list1[], int list2[], int k) {

// TODO: pass in the array sizes as parameters 
int m = 8; 
int n = 5;

// initialize array pointers such that i + j = k
int i = m/2;
int j = n/2; 
if (i + j + 2 < k) {
    while (i + j + 2 != k) {
        if (++i + j + 2 == k)
            break;
        if (i + ++j + 2 == k)
            break;
    }
} else if (i + j + 2 > k) {
    while (i + j + 2 != k) {
        if (--i + j + 2 == k)
            break;
        if (i + --j + 2 == k)
            break;
    }
}

// step forward in one array and step backward in another array
// decrement step size with every iteration until it is 0
int s = k/2; 
while (s > 0) {
    if (list1[i] < list2[j]) {
        if (m - 1 - i >= s &&
            j >= s) {

            i += s;
            j -= s;
        }
    } else {
        if (i >= s &&
            n - 1 - j >= s) {

            i -= s;
            j += s;
        }
    }
    s = s/2;
}

pair<int, int> r(i,j);
return r;
}

int main() {

int list1[] = {1, 4, 6, 7, 10, 11, 13, 27};
int list2[] = {2, 3, 20, 40, 60};

pair<int, int> test = smallestKElements(list1, list2, 6);
cout << test.first << "," << test.second << endl;

return 0;
}
Community
  • 1
  • 1
allenylzhou
  • 1,431
  • 4
  • 19
  • 36
  • Can you add some text explanation of your algorithm? I haven't fully digested it yet but it doesn't look anything like what I would use . – M.M May 23 '14 at 03:37
  • To fix your "TODO" hold the items in a `vector` instead of a C-style array – M.M May 23 '14 at 03:37
  • 1
    Note that although the accepted answer in the linked dupe doesn't seem to be quite correct, it looks like lambdapilgrim's is correct, including working for arrays of unequal length (and JF Sebastian's answer shows an implementation of that algorithm in C++). – Jerry Coffin May 23 '14 at 03:55
  • lambdapilgrim seems to have the right answer. I attempted the problem by doing concurrent binary search on both arrays but when the arrays are of unequal length, the loop invariant i + j = k doesn't hold so that approach doesn't work. – allenylzhou May 23 '14 at 05:18

1 Answers1

0

Ok, you could do something similar to this for each list, if I understood your problem:

std::nth_element(lst, lst + k, begin(lst) + list_size, std::greater<int>());

Keep in mind that you need the size of the list. You can do the same with the other array. This will modify the arrays, if you don't want to modify the arrays, make arrays of std::reference_wrapper and nth_element those.

Germán Diago
  • 7,473
  • 1
  • 36
  • 59