长度为N的数组可以包含值1,2,3，...，N ^ 2。是否有可能在O（n）时间排序？ [英] An array of length N can contain values 1,2,3 ... N^2. Is it possible to sort in O(n) time?

问题描述

鉴于长度N的阵列可以从范围从1到N ^ 2包含的值（N的平方），包括两个端点，值是一体的。是否有可能这个数组在O（n）时间排序？如果可能的话怎么办？

Given an array of length N. It can contain values from ranging from 1 to N^2 (N squared) both inclusive, values are integral. Is it possible to sort this array in O(N) time? If possible how?

编辑：这不是一门功课。

This is not a homework.

推荐答案

收件在碱N中的每整数，也就是每个x可以重新presented作为（X1，X2）其中x = 1 + X1 + X2 * N.现在，您可以两次计数排序，一旦x1和曾经在X2，产生的排序数组中的排序。

Write each integer in base N, that is each x can be represented as (x1, x2) with x = 1 + x1 + x2*N. Now you can sort it twice with counting sort, once on x1 and once on x2, resulting in the sorted array.

这篇关于长度为N的数组可以包含值1,2,3，...，N ^ 2。是否有可能在O（n）时间排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！