4

So, we have a list of N integers, from which we want to get K largest integers (unsorted). The problem is, this needs to be able to run in O(N + K). That's what stated in the assignment.

I've checked various algorithms and even made my own, but the best I can get is O((n-k)*k) which I don't think is close to O(N + K), unless I'm wrong.

Are there any algorithms out there that can do this in O(N + K) assuming the values in the list are pretty much random, and all positive? (We don't know the max value they can acheive)

Note that I need to find the K largest integers as in not the K-th largest but from N, K integers.

Example: N = 5, K = 2 Input: 5 6 8 9 3 Output: 9 8

Jack Avante
  • 1,405
  • 1
  • 15
  • 32
  • 2
    Possible duplicate of [Optimal algorithm for returning top k values from an array of length N](https://stackoverflow.com/questions/4956593/optimal-algorithm-for-returning-top-k-values-from-an-array-of-length-n) – Adam Sep 30 '19 at 23:18

2 Answers2

4

A selection algorithm is used to find the kth largest element. Median of Medians is an O(n) selection algorithm.

Therefore, there's a simple O(n) algorithm for your problem: Let KTH be the kth largest element as returned by your selection algorithm. This takes O(n) time. Scan the array and extract all elements >= KTH. This takes O(n) time.

Quickselect is another selection algorithm worth knowing about. It's based on quicksort, so it's only O(n) in the average case.

Adam
  • 16,808
  • 7
  • 52
  • 98
  • It's used to find the kth largest element, do I'd have to do this algorithm k times to get the top K largest integers from N right? Cause I need multiple, where K denotes how many. Wouldn't this still be O(N*K)? – Jack Avante Oct 01 '19 at 07:19
  • 1
    No. See second paragraph in the answer. – anatolyg Oct 01 '19 at 07:29
1

The idea is to, make a Binary Search Tree, which can be done in O(log N), though in worst case O(N) [where N - is total nodes/array elements in this case].

Now we can do inorder traversal, to get all elements in sorted order, which can be done O(N) [Proof: Complexities of binary tree traversals ]

Now traverse the sorted elements K-times (descending order);

Therefore, overall complexity will be: O(N) + O(N) + O(K) => O(N+K)

IMPLEMENTATION:

public class Solution{
static class BST{
    int val;
    BST left, right;

    public BST(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}
// making bst from the array elements
static BST add(BST root, int item) {
    if(root == null) return new BST(item);

    if(root.val > item)
        root.left = add(root.left, item);

    else root.right = add(root.right, item);

    return root;
}
// doing inorder to get all elements in sorted order
static void inorder(BST root, List<Integer> list) {
    if(root.left != null)
        inorder(root.left, list);

    list.add(root.val);

    if(root.right != null)
        inorder(root.right, list);

}
public static void main(String[] args) {
    //Example: N = 5, K = 2 Input: 5 6 8 9 3 Output: 9 8
    int [] a = {1, 9, 2, 7, 3, -1, 0, 5, 11};

    BST root = null;

    for(int i=0; i<a.length; i++) {
        root = add(root, a[i]);
    }
    List<Integer> list = new ArrayList<Integer>();
    inorder(root, list);

   // process the list K times, to get K-th largest elements        
}

NB: in case of Duplicate values, you have to make sub-list for each node!

Papai from BEKOAIL
  • 1,469
  • 1
  • 11
  • 17
  • 1
    inserting into a tree is (amortized) `O(log N)`, but you're inserting `N` elements, so total build time is `O(N log N)`. you then do `O(N)` more ops to pull items out of the tree and into a list, and then you do `O(K)` ops to just get the values out of the list again. hence time will be `O(N log N + N + K)` or, simplifying, `O(N log N + K)` – Sam Mason Oct 04 '19 at 12:41