SortedSearch.countNumbers(new int [] {1，3，5，7}，4)应该返回2，因为有两个小于4的数组元素

问题描述

需要更有效的方法

以下是结果:

• 示例案例:正确答案

• Example case: Correct answer

各种小型数组:正确答案

Various small arrays: Correct answer

sortedArray包含 lessThan 的性能测试:时间超出限制

Performance test when sortedArray contains lessThan: Timelimit exceeded

sortedArray不包含 lessThan 时的性能测试:超过了时间限制

Performance test when sortedArray doesn't contain lessThan: Time limit exceeded

以下是代码:

import java.util.Arrays;

public class SortedSearch {
    public static int countNumbers(int[] sortedArray, int lessThan) {

        Arrays.sort(sortedArray);
        int count =0;

        for(int num :sortedArray){

            if(num < lessThan)
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(SortedSearch.countNumbers(new int[] { 1, 3, 5, 7 }, 4));
    }
}

引用链接:在这里尝试

推荐答案

尝试以下代码

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) / 2;
        if (sortedArray[mid] < lessThan) {
            if (mid < sortedArray.length - 1 && sortedArray[mid + 1] < lessThan) { // check id next value is also valid
                start = mid + 1;
                continue;
            } else
                return mid + 1;
        }

        if (sortedArray[mid] >= lessThan) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return 0;

}

这篇关于SortedSearch.countNumbers(new int [] {1，3，5，7}，4)应该返回2，因为有两个小于4的数组元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！