Commitbf45d70

committed

kth smallest element in a sorted matrix

1 parent08e741e commitbf45d70Copy full SHA for bf45d70

File tree

+41

-0

lines changed

+41

-0

lines changed

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,41 @@`
	`1`	`+packagemedium;`
	`2`	`+`
	`3`	`+importjava.util.ArrayList;`
	`4`	`+importjava.util.Collections;`
	`5`	`+importjava.util.List;`
	`6`	`+/**378. Kth Smallest Element in a Sorted Matrix QuestionEditorial Solution My Submissions`
	`7`	`+Total Accepted: 5`
	`8`	`+Total Submissions: 7`
	`9`	`+Difficulty: Medium`
	`10`	`+Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.`
	`11`	`+`
	`12`	`+Note that it is the kth smallest element in the sorted order, not the kth distinct element.`
	`13`	`+`
	`14`	`+Example:`
	`15`	`+`
	`16`	`+matrix = [`
	`17`	`+ [ 1, 5, 9],`
	`18`	`+ [10, 11, 13],`
	`19`	`+ [12, 13, 15]`
	`20`	`+],`
	`21`	`+k = 8,`
	`22`	`+`
	`23`	`+return 13.`
	`24`	`+Note:`
	`25`	`+You may assume k is always valid, 1 ≤ k ≤ n2.*/`
	`26`	`+publicclassKthSmallestElementInASortedMatrix {`
	`27`	`+//brute force made it AC'ed, extreme test case needed for OJ`
	`28`	`+publicintkthSmallest(int[][]matrix,intk) {`
	`29`	`+List<Integer>list =newArrayList<Integer>();`
	`30`	`+intn =matrix.length;`
	`31`	`+for(inti =0;i <n;i++){`
	`32`	`+for(intj =0;j <n;j++){`
	`33`	`+list.add(matrix[i][j]);`
	`34`	`+ }`
	`35`	`+ }`
	`36`	`+Collections.sort(list);`
	`37`	`+returnlist.get(k-1);`
	`38`	`+ }`
	`39`	`+`
	`40`	`+//TODO: use heap and binary search to do it.`
	`41`	`+}`

Comments

(0)