我正在练习来自testdome.com的排序搜索任务
/**
* Implement function countNumbers that accepts a sorted array of unique integers and,
* efficiently with respect to time used, counts the number of array elements that are less than the parameter lessThan.
* <p>
* For example, SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4)
* should return 2 because there are two array elements less than 4.
*/
目前，根据该站点的数据，由于边缘情况和性能的原因，我的回答得分为50％，我试图就我可能需要添加的内容或采用其他方法获得意见。这是我的代码
public static int countNumbers(int[] sortedArray, int lessThan) {
int count = 0;
if(sortedArray == null) {
return 0;
}
List<Integer> numbers = new ArrayList<>();
for (int i = 0; i < sortedArray.length; i++) {
if (sortedArray[i] < lessThan) {
count++;
} else {
break;
}
}
return count;
}
当我在他们的环境中对其进行测试时得到的结果如下
示例案例：正确答案
各种小数组：正确答案
sortedArray包含lessThan时的
性能测试：超过时间限制sortedArray不包含lessThan时的性能测试超过：时间限制
所以即使我看不到这两个测试也可能导致两个性能测试失败，但我可以在这里得到建议
如果O(n)是给TLE。您需要比更快的东西O(n)。二进制搜索为O(logN)。
public static int countNumbers(int[] sortedArray, int lessThan) {
int start = 0;
int end = sortedArray.length - 1;
int mid = 0;
while (start <= end) {
mid = start + (end - start) / 2;
if (sortedArray[mid] < lessThan) {
if (mid < sortedArray.length - 1 && sortedArray[mid + 1] < lessThan) {
start = mid + 1;
continue;
} else {
return mid + 1;
}
}
if (sortedArray[mid] >= lessThan) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return 0;
}
或使用内置的二进制搜索：
Arrays.binarySearch(new int[]{1, 2, 4}, 3) + 1) * -1;
当找不到密钥时，它将返回负插入位置。为了将其转换为索引，我做了+ 1并乘以- 1使其为正。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句