FilesExpand file tree

 master

/

KthElementInArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (58 loc) · 1.6 KB

 master

/

KthElementInArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (58 loc) · 1.6 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

package com.interview.array;

import java.util.Arrays;

/**

* Kth largest element in an array.

* Use quickselect of quicksort to find the solution in hopefully O(nlogn) time.

* Test cases

* Sorted array

* Reverse sorted array

*/

public class KthElementInArray {

public int kthElement(int arr[],int k){

int low = 0;

int high = arr.length-1;

int pos =0;

while(true){

pos = quickSelect(arr,low,high);

if(pos == (k+low)){

return arr[pos];

}

if(pos > k + low){

high = pos-1;

}else{

k = k - (pos - low + 1);

low = pos+1;

}

}

}

private int quickSelect(int arr[],int low,int high){

int pivot = low;

low++;

while(low <= high){

if(arr[pivot] > arr[low]){

low++;

continue;

}

if(arr[pivot] <= arr[high]){

high--;

continue;

}

swap(arr,low,high);

}

if(arr[high] < arr[pivot]){

swap(arr,pivot,high);

}

return high;

}

private void swap(int arr[],int low,int high){

int temp = arr[low];

arr[low] = arr[high];

arr[high] = temp;

}

public static void main(String args[]){

int arr[] = {6, 2, 1, 6, 8, 9, 6};

KthElementInArray kthElement = new KthElementInArray();

System.out.print(kthElement.kthElement(arr, arr.length/2));

System.out.print(Arrays.toString(arr));

}

}