问题是根据字符串的长度对字符串数组进行排序。
例如
input = {"cat", "star", "act", "gid", "arts", "dog", "rats"}
output = {"cat", "act", "gid", "dog", "star", "arts", "rats"}
我是使用插入排序（使用字符串的长度而不是字符串本身）来完成的。我的问题是：有更好的方法吗？
我想到的另一种方法是-使用aTreeMap将每个字符串及其长度存储为值（假设字符串在给定数组中是唯一的）。然后根据其值对其进行排序。运行时间为O(nlogn)，空间复杂度为O(n)。您认为这是更好的方法吗？
编辑：对不起，您没有提到此-我想不使用Arrays.sort()或自定义比较器来执行此操作。
用于插入排序的代码示例：
public static String[] insertionSort(String[] arr) {
for(int i=1;i<arr.length;i++) {
int j = 0;
for(;j<i;j++) {
if(arr[j].length() > arr[j+1].length()) {
String temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
有许多更好的方法可以做到这一点。对于插入排序，我们说的是O（n ^ 2）。更好的排序算法将是诸如mergesort（更好的最坏情况）或quicksort（平均更好）之类的算法。由于这是基于长度的排序，因此可以采用多种方法。您将必须在某个时刻计算每个字符串的长度。您可以做的是创建一个整数数组，该数组对应于相同索引处的单词长度。然后，您可以在int上运行mergesort或quicksort，并确保同时翻转字符串。最终结果将是一个非递减的整数数组和一个非递减的字符串数组。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句