CODEWITHSUNDEEP
javaarraysalgorithmsortingdivide-and-conquer
DaryEiki
DaryEiki

Reputation: 3

Divide and conquer - k element of unsorted array

I am having a problem trying to implement an algorithm using Divide and conquer.

Given an unsorted array T v[] find de v[k] element of that array as if the array was sorted but without sorting the array v.

For example, if k = 3 and v = {2, -1, -6, 7, 4} the k element of that array is 2.

Since I can't edit the passed array I can't think another way to sort the array without saving it on another local variable or trying to divide the array like quicksort and returning the position where the last element of v should be.

And if it helps, this is my code:

public static <T extends Comparable<? super T>> T kesimoRec(T v[], int izq, int der, int k) {
    if(izq < der){
    int inf = izq-1;
    T pivote = v[der];
       for(int i = izq; i < der; ++i){
           if(pivote.compareTo(v[i]) >= 0){
               ++inf;
           }
       }
       ++inf;
       if(inf > izq + k-1){
           return (kesimoRec(v, izq, inf-1, k));
       }else if( inf < izq + k-1){
           return (kesimoRec(v, inf+1, der, k-inf+izq-1));
       }else{
           return v[inf];
       }
    }else{
        return v[der];
    }
}

Upvotes: 0

Views: 1812

Answers (2)

Monicalh
Monicalh

Reputation: 101

With divide and conquer

public static <T extends Comparable<? super T>> T kesimoRec(T v[], int izq,
            int der, int k) {
        if (izq == der) {
            return v[izq];
        }
        int pivote = partir(v, v[der], izq, der);
        if (k == pivote) {
            return v[k];
        } else if (k < pivote) {
            return kesimoRec(v, izq, pivote - 1, k);
        } else {
            return kesimoRec(v, pivote + 1, der, k);
        }
    }

Upvotes: 0

Ealon
Ealon

Reputation: 4898

Why you use divide and conquer?

I suggest that you use a PriorityQueue. You can google more about PriorityQueue. Once you understand how it works, you will find it is easy to come up with a solution. My java code:

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(nums.length);

        for (int num : nums) {
            queue.offer(num);
        }

        for (int i = 0; i < nums.length - k; i++) {
            queue.poll();
        }

        return queue.peek();
    }
}

Hmm, sorry, my solution is to find the kth largest, but you can modify it to find the kth smallest.

Upvotes: 1

Related Questions