这个findRange方法的大O. [英] Big O of this findRange method

问题描述

我正在试图弄清楚下面显示的findRange的运行时复杂性，它找到了排序数组a和密钥的底部和顶部索引。

如果找不到密钥则返回 - 1 -1。



int [] a = new int [] {1,2,3,3,5,5,5,5};

findRange（a，5）=> 5 8



我想出解决方案O（2 * log（#times_key_appears）* log n）=> O（（log n）^ 2）

这是正确的吗？

那里有更好的算法解决方案吗？

I'm trying to figure out the runtime complexity of findRange shown below, which finds the bottom and top index given a sorted array a and key key.
If key is not found then return -1 -1.

int[] a = new int[] { 1, 2, 2, 3, 3, 5, 5, 5, 5 };
findRange(a, 5) => 5 8

I'm coming up with the solution O(2 * log(#times_key_appears)* log n) => O((log n)^2)
Is this correct?
Is there a better algorithmic solution out there?

public void findRange(int[] a, int key) {
    int bsLeft = bsLeft(a, 0, a.length , key, -1);
    System.out.print(bsLeft);
    System.out.print(" ");
    System.out.println(bsRight(a, bsLeft, a.length , key, -1));
}

public int bsLeft(int[] a, int startIndex, int lastIndex, int key, int found){
    int value = Arrays.binarySearch(a, startIndex, lastIndex, key);
    if (value < 0) {
        return found;
    }
    return bsLeft(a, startIndex, value -1, key, value);
}

public int bsRight(int[] a, int startIndex, int lastIndex, int key, int found){
    int value = Arrays.binarySearch(a, startIndex , lastIndex, key);
    if (value < 0) {
        return found;
    }
    return bsRight(a, value + 1, lastIndex, key, value);
}

推荐答案

我必须了解您的问题才能知道最佳解决方案。



您是否可以自由更改存储数据的格式？最好将这些数据预处理到我在下面提到的表单中一次。



例如，您只能存储唯一值并且有一个存储计数的并行容器在每个指数。当然，不是有一个平行的容器，你可以有一个包含项目和计数的结构。



项目：1,2,3,5

计数：1,2,2,5



您可以在O（log2 N）时间内使用常规二进制搜索找到该项目，并且然后只为你找到的项目取5（索引为3），并添加计数以找到范围的顶部，例如3 + 5 = 8。 b $ b

你所拥有的结构的问题在于它使得使用二进制搜索变得困难 - 我会重新安排数据更好。



顺便说一句，如果数据发生变化，即你经常从列表中插入和/或删除项目，那么红黑树将是一个更好的解决方案，因为不断插入和排序数组效率低下。即使在这种情况下，我认为存储具有项目的结构和项目的计数也是最好的。

I'd have to understand your problem to know the best solution.

Are you free to change the forms of your stored data? It might best to preprocess that data one time into the form I mention below.

For example, you could only store unique values and have a parallel container that stores the count at each index. Of course, rather than have a parallel container, you could have a structure that contains the item and the count.

Item: 1, 2, 3, 5
Count: 1, 2, 2, 5

You can find the item using a regular binary search in O(log2 N) time, and then merely take that index for the item you found (for 5, the index would be 3), and add the count to find the top of the range, which for your example would be 3 + 5 = 8.

The issue with the structure you have is that it makes using a binary search difficult - I'd rearrange the data to be better.

By the way, if the data changes, that is, you are inserting and/or removing items from the list often, then a red-black tree would be a better solution as constantly inserting and sorting the array would be inefficient. Even in that case, I think storing a structure with the item and the count of the item would be best.

这篇关于这个findRange方法的大O.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！