java - 查找元素是否存在于给定范围内

Question

我有两个数组 A 和 B。而且我必须找到数组 C 所需的元素数以适应特定长度。

Length = B[i]-A[i]

例如:

A[0] = 1    B[0] = 4
A[1] = 4    B[1] = 5
A[2] = 5    B[2] = 9
A[3] = 8    B[3] = 10
and 
C[0] = 4
C[1] = 6
C[2] = 7
C[3] = 10
C[4] = 2

答案是4。

解释:

C[0] is falling in the range of (A[0],B[0]) and (A[1],B[1])
C[1] is falling in the range of (A[2],B[2]) 
C[2] is of no use
C[3] is falling in the range of (A[3],B[3])
so the total is 4

我的方法:
传统方法:简单循环数组 A 中 C 的每个元素，如果在范围内找到则设置 A[i] 的值 和 B[i] 减去无穷大或删除它们(对于 Arraylist)。

• 时间复杂度是一个问题，因此不是一个好的方法。

HashTable:将值存储在哈希表中，A[i] 为键，B[i] 为值。然后找到给定 C[i] 的元素并删除键。我认为这不是一个好方法

请为此提供一个有效的算法。

Answer 1

如果输入范围已经从小到大排序(B[i] <= A[i+1]):

int bottomRangeIndex = 0;
int topRangeIndex = numberOfABRangesYouHave - 1;
int answerCounter = 0;

C.sort(); // Sort C so that it goes from smallest to largest number.

for number in C: {
    if (number < A[bottomRangeIndex]) {
        continue;
    } else if (number > B[topRangeIndex]) {
        return answerCounter;
    } else {
        while ((number > B[bottomRangeIndex++]) && (bottomRangeIndex <= topRangeIndex)) {
            // Just keeps incrementing bottomRangeIndex.
        }
        if (bottomRangeIndex > topRangeIndex) {
            return answerCounter;
        } else {
            answerCounter++;
            bottomRangeIndex++;
        }
    }
}

这可能有一些我没有想到的错误，但基本上它的作用是:

1. C 类。我知道你说你不能这样做，但我不明白为什么，除非这是作业问题。
2. 如果来自 C 的数字完全落在 A、B 范围之外，则跳过检查 A、B 范围内的任何内容。如果当前数字大于 A、B 范围内的最大数字 (B[topRangeIndex])，则返回当前答案计数器，因为来自 C(已排序)的更多元素不可能再次出现在 A、B 范围内。
3. 由于 C 已排序并且当前数字大于所有 A、B 范围中的底部元素，因此开始检查 C 中的数字是否落在每个 A 范围的 B 端内。被检查的数字始终是 C 中的最小元素，因此如果它未能落入 A 范围的 B 端，则永远不应再次检查 A、B 范围，因此 bottomRangeIndex 递增。
4. 如果 while 循环消除了每个范围，我们就完成了检查(C 中的当前元素大于任何 A、B 范围中的最大数字，我们不需要检查任何其他内容。
5. 如果 C 中被检查的数字不大于 A、B 范围末尾的数字(位于 bottomRangeIndex)，则该 A、B 范围包含来自 C 的元素。我们递增答案计数器，移动bottomRangeIndex向上，继续。

试试这个，看看它是否有效。如果这是家庭作业并且您真的无法对 C 进行排序，那么您可以修改它以通过少量调整为您提供正确的答案，但我不会说如何...