K Spaced Array Sorting
An array is ordered from small to large every k digits, ie arr[i] <= arr[i + k] <= arr[i + 2 * k] <= …. Sort the array from small to large. We expect you to write an algorithm whose time complexity is O(n * logk).
- 0 <= arr[i] <= 2^31 – 1
- 1 <= |arr| <= 10^5
- 1 <= k <= 10^5
Given arr = [1,2,3], k = 1, return [1,2,3]. Explanation: The sorted array is [1,2,3].
Given arr = [4,0,5,3,10], k = 2, return [0,3,4,5,10].
Explanation: The sorted array is [0,3,4,5,10].
Credits To: lintcode.com
Leave me comments, if you have better ways to solve.
// Blog link: https://code.dennyzhang.com/k-spaced-array-sorting