7 ms·
Input: arr = [7, 4, 6, 3, 9, 1] k = 2 Output: k’th smallest element in the array is 4 Am I missing something... shouldn't the k'th smallest element in this ar
by dwils098 10y ago
Input: arr = [7, 4, 6, 3, 9, 1]
k = 2
Output: k’th smallest element in the array is 4
Am I missing something... shouldn't the k'th smallest element in this array be 3, given that k=2?
- coder007 10y agohere, numbering starts from 0 same as std::nth_element
- deleted 10y ago[deleted]
- CarolineW 10y agoSort the array: L = [7, 4, 6, 3, 9, 1] -> L = [1, 3, 4, 6, 7, 9] Now L[k] = L[2] = 4. The notation is potentially misleading, but consistent with this interpretation. EDIT: Ah, I was completely wrong. List : [7, 4, 6, 3, 9, 1] Index: 1 2 3 4 5 6 The smallest element is 1, the second smallest element is 3, the index of the second smallest element counting from 1 is 4. This is deeply, deeply confusing. Badly expressed, and a very poor example.
- dwils098 10y agoContext can be clarified by writing: "Quickselect is a selection algorithm to find the INDEX OF THE kth smallest element in an unordered list. It is closely related to the quicksort sorting algorithm."
- coder007 10y agoit doesn't return the index, rather the element itself..
- dwils098 10y agoTrue. This is what I meant by confusing, without properly defining the variables at play, in this context, k is the index of the element of the ordered list, and not the kth smallest element. Semantics, I agree, but confusing nonetheless. Or in other words, how do we define k?
- deleted 10y ago[deleted]