LintCode: K Spaced Array Sorting

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).

Notice

  • 0 <= arr[i] <= 2^31 – 1
  • 1 <= |arr| <= 10^5
  • 1 <= k <= 10^5

Example

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].

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/k-spaced-array-sorting

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.