CODEWITHSUNDEEP
javaarraysalgorithmsorting
Leon kong
Leon kong

Reputation: 149

Given two sorted lists (or arrays) and a number k, create an algorithm to fetch the least k numbers of the two lists

Need to find the first 3 smallest number in given two sorted array. I supposed that two array should merge into one first and sort it in order to fetch the first 3 smallest number. Can anyone help me with the merge and sort part or provide some advice, any help will appreciate.

This is where i reached now, I only can get the smallest number ( not first 3, just one).

public class MergeandSort {


public static void main(String[] args) {
    int[] set1 = {1,2,6,9,18};
    int[] set2 = {2,3,7,10,21,30};

    int smallest = set1[0];
    int smallests = set2[0];

    for(int i=0; i < set1.length; i++){
        if(set1[i] < smallest)
            smallest = set1[i];
    }
    for(int k=0; k < set2.length; k++){
        if(set2[k] < smallests)
            smallests = set2[k];
    }

    System.out.println("Smallest Number in Set 1 is : " + smallest);
    System.out.println("Smallest Number in Set 2 is : " + smallests);


}

}

Upvotes: 1

Views: 1239

Answers (4)

Pushan Gupta
Pushan Gupta

Reputation: 3825

If the arrays are already sorted, just implement the merging technique of merge sort with the limitation in while condition that it should run only k times (in this case 3), but dont forget to check that size of sets are less than k or not! 

        int k = 0,i = 0,j = 0;

        while (k<3 && k<set1.length && k<set2.length )
        {
            if (set1[i] <= set2[j])  
            {
                final_set[k] = set1[i];
                i++;
            }
            else
            {
                final_set[k] = set2[j];
                j++;
            }
            k++;
        }

         while (k<3 && k<set1.length) {
           final_set[k]=set1[i];
           k++;
           i++;
       }   

      while (k<3 && k<set2.length) {
           final_set[k]=set1[j];
           k++;
           j++;
       }

Upvotes: 1

thrust
thrust

Reputation: 215

public class MergeandSort {

    public static void main(String[] args) {
        int[] set1 = {1,2,6,9,18};
        int[] set2 = {2,3,7,10,21,30};
        int[] sorted = new int[k];

        int smallest = set1[0];
        int smallests = set2[0];

        int i = 0, j = 0, c = 0;
        while(i < set1.length && j < set2.length && c < k){
            if (set1[i] < set2[j])
                sorted[c++] = arr1[i++];
            else
                sorted[c++] = arr2[j++];

        while (i < set1.length && c < k)
            sorted[c++] = arr1[i++];
        while (j < set2.length && c < k)
            sorted[c++] = arr2[j++];

        System.out.println(sorted);
    }
}

where k is the count of sorted numbers you want

Upvotes: 0

Florianisme
Florianisme

Reputation: 1

That would not work as:

Array1 = {1,3,5}

Array2 = {2,3,4}

Correct solution: {1,2,3}

Output of your solution: {1,3,4}

Upvotes: 0

Eran
Eran

Reputation: 393781

The arrays are already sorted, so you don't have to iterate over the entire arrays to find the 3 smallest numbers.

  • You just have to start iterating over both arrays at the same time (i.e. in the same loop).
  • In each iteration you compare the current two elements of the two arrays (starting at the 2 elements at the 0 index) and take the smaller of them
  • Then you advance the index of the array from which you took the smallest number.
  • Once you reach 3 elements (after 3 iterations), you break out of the loop.

Here's some pseudo code to get you started:

int i = 0;
int j = 0;
int c = 0;
int[] lowest3 = new int[3];
while (true) {
    find the smaller of set1[i] and set2[j] and put it in lowest3[c]
    if set1[i] is smaller, increment i
    otherwise increment j
    increment c
    if (c==3) // you are done
        break;
}
the lowest3 array now contains the 3 lowest numbers of both arrays

Of course you can swap 3 with any k. You just have to make sure that i is always smaller than set1.length and j is always smaller than set2.length.

Upvotes: 4

Related Questions