My solution is O(NlogN),but I thought there may be some solutions use only O(N) time, thank you for your sharing!