如何降低该方法的时间复杂度？

Question

首先，我对这次的不愉快感到抱歉 上下文：我有一个有 2 个字段的类，其中一个是表示日期的整数（对于这个特定问题，它必须是整数）。我还有一个方法，可以在整数数组中进行二分搜索，时间复杂度为 O(Log(N))。 我需要创建一个方法来接收两个日期（初始日期和最终日期）以及来自上述类的对象列表。该列表可以是 ArrayList 或 LinkedList。目标是使用二分搜索方法找出所需日期范围内的列表中存在多少个该类的对象（最小值 0 和最大值 2，根据定义设置）。

这个方法的时间复杂度一定是O(Log(N))，但我不知道如何解决它。我所有的解决方案的时间复杂度都是 O(N) 甚至更糟。我将把方法留在下面。 我的想法是，我需要在恒定时间内将日期值传递给数组，但我什至不知道这是否可以实现。

public static int countEvents(int initialDate, int endDate, List<Event> list) {
    int n = list.size(), i = 0;
    int[] dates = new int[n];

    for (Event event : list) {
        dates[i] = event.getDate();
        i++;
    }

    int InitialPos = binarySearch(dates, initialDate);
    int EndPos = binarySearch(dates, endDate + 1);

    return EndPos - InitialPos;
}

谢谢您的帮助！

Answer 1

您不需要创建一个新数组

dates

，它保存

list

变量中列表中的整数日期值。该数组的创建和填充的时间复杂度为

O(N)

。相反，您将变量

list

中已存在的列表传递给二分搜索方法。然后，在二分搜索方法中，您可以使用

getDate()

方法访问日期，并将其与给定的搜索值进行比较。这样您只需要两次

O(log(N))

调用。