linearTimeSort
Given an array of length n with the maximum value k of the elements equal or smaller than n (k<=n) , your task is to sort the array in O(k + n) time and out put it.
Note: Do not not use built-in sorting functions bacause they will take O(n log n) which is a lot worse than the requirement of the task.
Example
- For
arr = [1,2,3,4,3,4], the output should belinearTimeSort(arr) = [1,2,3,3,4,4]
Input/output:
- Input: array of integers arr
Guaranteed constraints:1 <= arr.length <= 10^6 - Output: array of integers
The sorted array.
Post Comment