FilesExpand file tree

 master

/

FindKthNumber.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

50 lines (41 loc) · 1.52 KB

 master

/

FindKthNumber.java

Top

File metadata and controls

• Code
• Blame

50 lines (41 loc) · 1.52 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

package Algorithms;

public class FindKthNumber {

public static void main(String[] str) {

int A[] = {1,2,3,3};

int B[] = {3,3,7,8};

FindKthNumber fn = new FindKthNumber();

double ret = fn.findMedianSortedArrays(A, B);

System.out.println(ret);

}

public double findMedianSortedArrays(int A[], int B[]) {

int len = A.length + B.length;

double ret = findKth(A, 0, B, 0, 6);

return ret;

/*

if (len % 2 == 0) {

return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0 ;

} else {

return findKth(A, 0, B, 0, len / 2 + 1);

}*/

}

// find kth number of two sorted array

public static int findKth(int[] A, int A_start, int[] B, int B_start, int k){

if(A_start >= A.length)

return B[B_start + k - 1];

if(B_start >= B.length)

return A[A_start + k - 1];

if (k == 1)

return Math.min(A[A_start], B[B_start]);

int A_key = A_start + k / 2 - 1 < A.length

? A[A_start + k / 2 - 1]

: Integer.MAX_VALUE;

int B_key = B_start + k / 2 - 1 < B.length

? B[B_start + k / 2 - 1]

: Integer.MAX_VALUE;

if (A_key < B_key) {

return findKth(A, A_start + k / 2, B, B_start, k - k / 2);

} else {

return findKth(A, A_start, B, B_start + k / 2, k - k / 2);

}

}

}