长度为N的数组可以包含值1,2,3…N ^ 2。是否可以按O（n）时间排序？

浏览：74日期：2024-02-18

如何解决长度为N的数组可以包含值1,2,3…N ^ 2。是否可以按O（n）时间排序？？

将每个整数写入基数N，即每个x可以表示为（x1，x2），其中x = 1 + x1 + x2 *N。现在，您可以使用计数排序对其进行两次排序，一次在x1上，一次在x2上，从而生成已排序的数组。

解决方法

给定长度为N的数组。它可以包含从1到N ^ 2（N平方）（包括两个端点）的值，这些值是整数。是否可以在O（N）时间对该数组进行排序？如果可能的话如何？

编辑：这不是家庭作业。

相关文章：
1. javascript - 关于input="file"，重复选择同一文件时不触发change事件的问题2. javascript - var x = "[{’a’:’xx’},{’b’:’xxx’}]";如何在js中解析成json对象3. javascript - 在移动端input type="number" 键盘没法弹起4. javascript - type="date"的默认值能改变为当天日期吗5. mysql - sphinx查询 "中国" 时也能查询到 "中华人民共和国"6. solaris基础和常用知识 (2)7. html5 - 有可以一次性把所有 css外部样式转为html标签内style=" "的方法吗?8. mysql 使用 join 还是 "," 进行多表查询？？？9. mysql - 使用hibernate连接数据库时,数据库版本过高不支持关键字"type" ；10. javascript - 一个字符串转换成数字,例子就是a="2,322.222",b=’1,211.21’,如何在angualr中执行相减