DEV Community
·
3011. 判断数组是否可以排序
💡
原文英文，约900词，阅读约需4分钟。
📝
内容提要
给定一个正整数数组，允许交换相邻具有相同设置位数的元素，判断数组是否可以排序。例如，数组[8,4,2,30,15]可以排序为[2,4,8,15,30]，返回true；而数组[3,16,8,4,2]无法排序，返回false。
🎯
关键要点
-
给定一个正整数数组，允许交换相邻具有相同设置位数的元素，判断数组是否可以排序。
-
示例1: 输入[8,4,2,30,15]可以排序为[2,4,8,15,30]，返回true。
-
示例2: 输入[1,2,3,4,5]已经排序，返回true。
-
示例3: 输入[3,16,8,4,2]无法排序，返回false。
-
示例4: 输入[75,34,30]无法排序，返回false。
-
解决方案步骤包括：统计每个数字的设置位数，按设置位数分组，分别排序每个组，最后合并并检查是否已排序。
-
时间复杂度为O(n log n)，空间复杂度为O(n)。
❓
延伸问答
如何判断一个数组是否可以排序？
通过允许交换相邻具有相同设置位数的元素来判断数组是否可以排序。
给定数组[8,4,2,30,15]，它可以排序吗？
可以，返回true。
时间复杂度和空间复杂度分别是多少？
时间复杂度为O(n log n)，空间复杂度为O(n)。
如何实现数组的排序判断？
统计每个数字的设置位数，按设置位数分组，分别排序每个组，最后合并并检查是否已排序。
数组[3,16,8,4,2]能否排序？
不能，返回false。
设置位数是什么？
设置位数是指一个数字的二进制表示中值为1的位的数量。
➡️
