algorithm - 在一维数组中查找有界最近邻

Question

假设我们有一些 bool 值数组:

A = [0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 ... 0]

该数组是通过对数据流执行分类来构造的。数组中的每个元素对应于给定一小部分数据的分类算法的输出。答案可能包括重组数组以提高解析效率。

该数组是伪随机的，因为 1 和 0 的组往往成串存在(但不一定总是)。

给定一些索引i，找到最接近A[i]的至少由n个零组成的组的最有效方法是什么？对于简单的情况，取n = 1。

编辑:组应该至少 n 个零。同样，对于简单的情况，这意味着至少 1 个零。

EDIT2:此搜索将执行 o(n) 次，其中 n 是数组的大小。 (具体来说，它的 n/c，其中 c 是某个固定的持续时间。

Answer 1

在此解决方案中，我组织了数据，以便您可以使用二分搜索 O(log n) 来查找至少具有特定大小的最近组。

我首先从数组中创建零组，然后将每组零放入包含大小 s 或更大的所有组的列表中，这样当您想要找到最近的 s 组时s 或更大，然后您只需在包含大小为 s 或更大的所有组的列表中运行二分搜索。

缺点在于将组放入列表的预处理，需要 O(n * m) (我想，请检查我) 时间和空间效率，其中 n 是零组的数量，m 是组的最大大小，尽管实际上效率可能更好。

这是代码:

---

public static class Group {
    final public int x1;
    final public int x2;
    final public int size;

    public Group(int x1, int x2) {
        assert x1 <= x2;
        this.x1 = x1;
        this.x2 = x2;
        this.size = x2 - x1 + 1;
    }

    public static final List<Group> getGroupsOfZeros(byte[] arr) {
        List<Group> listOfGroups = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                int x1 = i;
                for (++i; i < arr.length; i++)
                    if (arr[i] != 0)
                        break;
                int x2 = i - 1;
                listOfGroups.add(new Group(x1, x2));
            }
        }
        return Collections.unmodifiableList(listOfGroups);
    }

    public static final Group binarySearchNearest(int i, List<Group> list) {
        { // edge cases
            Group firstGroup = list.get(0);
            if (i <= firstGroup.x2)
                return firstGroup;
            Group lastGroup = list.get(list.size() - 1);
            if (i >= lastGroup.x1)
                return lastGroup;
        }
        int lo = 0;
        int hi = list.size() - 1;
        while (lo <= hi) {
            int mid = (hi + lo) / 2;
            Group currGroup = list.get(mid);
            if (i < currGroup.x1) {
                hi = mid - 1;
            } else if (i > currGroup.x2) {
                lo = mid + 1;
            } else {
                // x1 <= i <= x2
                return currGroup;
            }
        }

        // intentionally swapped because: lo == hi + 1
        Group lowGroup = list.get(hi);
        Group highGroup = list.get(lo);
        return (i - lowGroup.x2) < (highGroup.x1 - i) ? lowGroup : highGroup;
    }
}

---

注意: GroupsBySize 可以改进，如 @maraca 所描述，仅包含每个不同组大小的 Group 列表。明天我会更新。

public static class GroupsBySize {
    private List<List<Group>> listOfGroupsBySize = new ArrayList<>();

    public GroupsBySize(List<Group> groups) {
        for (Group group : groups) {
            // ensure internal array can groups up to this size
            while (listOfGroupsBySize.size() < group.size) {
                listOfGroupsBySize.add(new ArrayList<Group>());
            }
            // add group to all lists up to its size
            for (int i = 0; i < group.size; i++) {
                listOfGroupsBySize.get(i).add(group);
            }
        }
    }

    public final Group getNearestGroupOfAtLeastSize(int index, int atLeastSize) {
        if (atLeastSize < 1)
            throw new IllegalArgumentException("group size must be greater than 0");
        List<Group> groupsOfAtLeastSize = listOfGroupsBySize.get(atLeastSize - 1);
        return Group.binarySearchNearest(index, groupsOfAtLeastSize);
    }
}

---

public static void main(String[] args) {
    byte[] byteArray = null;

    List<Group> groups = Group.getGroupsOfZeros(byteArray);
    GroupsBySize groupsBySize = new GroupsBySize(groups);

    int index = 12;
    int atLeastSize = 5;
    Group g = groupsBySize.getNearestGroupOfAtLeastSize(index, atLeastSize);

    System.out.println("nearest group is (" + g.x1 + ":" + g.x2 + ") of size " + g.size);
}