Results 1 to 6 of 6
  1. #1
    jmmjm is offline Member
    Join Date
    Nov 2008
    Posts
    1
    Rep Power
    0

    Default finding the largest k numbers in an array without sorting the whole list?

    Hi, I need help with my assignment.

    I need to write a program to find the largest k numbers in the array.
    eg. array: 12, 9, 36, 3, 0, 33
    k = 3
    output = 12, 36, 33

    Here are the constraints:
    1. I can't sort the whole list and then pick out the largest k numbers
    but can sort part of the data
    2. output of k largest items doesn't need to be sorted.
    3. the running time should run better than O(nlogn) , n is the size of the array.

    Here is what I am going to do.
    1. first, pick the first k numbers in the data and store them in another array of size k, called HEAP
    2. sort the HEAP of size k, which takes klogk time when using the quicksort.
    3. loop over the rest n-k numbers in the original array, for each number, compare it to the smallest number in the HEAP array, if smaller than it, discard it, if larger than it, update the smallest number in the HEAP array with this number.
    4. If after the updating, the order of the numbers in the HEAP array has changed, then resort them, resorting takes logk time when using heap sort. (I am not sure about the running time here...)
    5. then worst case running time should be klogk + (n - k) * klogk = nlogk <= nlogn

    but using this implementation, the k largest numbers will be sorted at the end. My question is that is there any better way to do it without sorting anything? or the largest k numbers are not sorted at the end?

    Sorry for the long description. Thanks in advance.

  2. #2
    prometheuzz is offline Member
    Join Date
    Nov 2008
    Posts
    4
    Rep Power
    0

    Default

    "Part of the data" is a rather vague term. A part of the data is the entire array except the first element. So sort that "part" which will get you [12, 0, 3, 9, 33, 36]. Then get the largest k numbers ([9, 33, 36]) and check if the first number (12 in this case) is larger than the smallest of your k numbers (9 in this case). If so, remove the smallest of the k numbers and add the first value from your original array. You now have [12, 33, 36].
    O(n*log(n))

    When crossposting, please provide a link to your other post(s). That way people can first check if you've been answered elsewhere before answering you.
    http: //forums.sun.com/thread.jspa?threadID=5346235
    Last edited by prometheuzz; 11-09-2008 at 11:24 AM.

  3. #3
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  4. #4
    StormyWaters is offline Senior Member
    Join Date
    Feb 2009
    Posts
    305
    Rep Power
    6

    Default

    pseudocode:

    numberArray[]//The array of numbers to grab the largest k numbers

    sortedArray[]//Create an array of size k

    Java Code:
    for (int i = 0; i < numberArray.length(); i ++){//For all the numbers in your given array
        int temp = numberArray[i];//Get the first number
            for (int j = 0; j < sortedArray.length(); j ++){//For all the spots you can place the number
                if (!sortedArray[j].equals(null)){//If there currently is a number there
                    int currentValue = sortedArray[j]; //Get the current number set
                    if (currentValue < temp){//If the number in the given array is greater then the current number there
                        sortedArray[j] = temp;//Set that spot to the number in the given array
                        temp = currentValue; //Set the number to check the additional spots to the number that was there
                    }
                } else { //There is no number there currently
                    sortedArray[j] = temp;//Set the number to the empty spot
                    break;//Break out of the for loop to make sure the other empty spots are not filled with the number
                }
            }
        }
    }

  5. #5
    toadaly is offline Senior Member
    Join Date
    Jan 2009
    Posts
    671
    Rep Power
    6

    Default

    What I would do, is search the list for the largest number, remove it, and then do that (k-1) more times.

  6. #6
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

Similar Threads

  1. Finding Largest Prime Factor
    By perito in forum New To Java
    Replies: 7
    Last Post: 11-08-2010, 08:25 PM
  2. Finding the largest number in an array
    By starchildren3317 in forum New To Java
    Replies: 14
    Last Post: 11-03-2010, 06:49 AM
  3. Converting array to list and sorting it
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 10:36 PM
  4. Finding largest and smallest integer
    By mlhazan in forum New To Java
    Replies: 2
    Last Post: 01-12-2008, 10:30 PM
  5. Finding largest no
    By bugger in forum New To Java
    Replies: 11
    Last Post: 11-29-2007, 12:49 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •