fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.     public static int findKthSmallest (int[] array, int k) {
  11.         if (array == null || array.length == 0 || k <= 0 || k > array.length) {
  12.             throw new IllegalArgumentException("Invalid input");
  13.         }
  14.  
  15.         return select(array, 0, array.length - 1, k - 1);
  16.     }
  17.  
  18.     private static int select (int[] array, int start, int end, int k) {
  19.         if (start == end) {
  20.             return array[start];
  21.         }
  22.  
  23.         int pivotIndex = partition(array, start, end);
  24.         if (k == pivotIndex) {
  25.             return array[k];
  26.         } else if (k < pivotIndex) {
  27.             return select(array, start, pivotIndex - 1, k);
  28.         } else {
  29.             return select(array, pivotIndex + 1, end, k);
  30.         }
  31.     }
  32.  
  33.     private static int partition (int[] array, int start, int end) {
  34.         int pivot = array[end];
  35.         int i = start - 1;
  36.  
  37.         for (int j = start; j < end; j++) {
  38.             if (array[j] <= pivot) {
  39.                 i++;
  40.                 swap(array, i, j);
  41.             }
  42.         }
  43.  
  44.         swap(array, i + 1, end);
  45.         return i + 1;
  46.     }
  47.  
  48.     private static void swap (int[] array, int i, int j) {
  49.         int temp = array[i];
  50.         array[i] = array[j];
  51.         array[j] = temp;
  52.     }
  53.  
  54.     public static void main (String[] args) {
  55.         int[] array = { 7, 10, 4, 3, 20, 15 };
  56.         int k = 3;
  57.  
  58.         int kthSmallest = findKthSmallest(array, k);
  59.         System.out.println("The " + k + "th smallest element is: " + kthSmallest);
  60.     }
  61. }
Success #stdin #stdout 0.14s 39088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The 3th smallest element is: 7
https://ideone.com/Uk8Iww
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!