Лучший алгоритм для нахождения количества повторений элемента, учитывая отсортированный массив с повторяющимися элементами no. времен

Question

Я пытался выполнить бинарный поиск по данному элементу и обходил его влево и вправо, пока он не получил элемент, больший или меньший, чем он, но он идет до O (n) временной сложности, если все элементы одинаковы. Может есть какой-нибудь лучший алгоритм?

Answer 1

Вы можете использовать бинарный поиск, который находит нижнюю границу диапазона (и / или верхнюю границу) и выполнять бинарный поиск для нижней границы и либо верхней границы, либо нижней границы диапазона элементов, один больше, чем тот, о котором вы заботитесь.

Редактировать: большая часть кода, который я видел для нахождения нижней границы, (я считаю) немного сложнее, чем действительно необходимо.

int *find(int *left, int *right, int val) {
    assert(left<right);
    while (left < right) {
        int *middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;
}

Answer 2

Выполнить два двоичных поиска:

В первом поиске вы выбираете левую половину, если средний элемент равен искомому элементу.

Во втором поиске вы выбираете правую половину, если средний элемент равен искомому элементу.

Пример кода на Java:

class Test {

    public static int findElem(int[] arr, int elem, int l, int h,boolean first) {
        if (h - l <= 1)
            return first ? (arr[l] == elem ? l : h) : (arr[h] == elem ? h : l);

        int m = l + (h - l) / 2;

        if (arr[m] < elem || (arr[m] == elem && !first))
            return findElem(arr, elem, m, h, first);

        return findElem(arr, elem, l, m, first);
    }

    public static int findElem(int[] arr, int elem, boolean first) {
        return findElem(arr, elem, 0, arr.length, first);
    }

    public static void main(String[] args) {
        int[] arr = { 0, 1, 2, 2, 2, 3, 3, 4, 4, 5 };

        int elem = 2;

        System.out.println("First index: " + findElem(arr, elem, true));
        System.out.println("Last index : " + findElem(arr, elem, false));
    }
}

Answer 3

Вы должны выполнить бинарный поиск для первого и последнего элементов вашей подходящей последовательности. Если вы используете C ++, в STL есть такие функции, как lower_bound и upper_bound, которые позволяют вам это делать. В противном случае это простая модификация алгоритма.

В качестве альтернативы вы можете использовать 3 бинарных поиска:

1. Двоичный поиск любого элемента, который соответствует вашему значению
2. Двоичный поиск левой части вашего диапазона
3. Двоичный поиск правой части диапазона

Однако, возможность сделать последние 2 означает, что вы достигли первого решения (найдя нижнюю / верхнюю границы)

Answer 4

Предположим, у вас есть отсортированный массив a из n элементов типа T.Тогда для определенного элемента x вы можете найти номер его повторения следующим образом:

T* ub = upper_bound( a, a + n, x );
int answer = ub - lower_bound( a, ub, x );

Сложность, очевидно, O(logn).Когда все элементы одинаковы или нет элемента x в a, upper_bound вернется к a+n и lower_bound будет работать на всем интервале, что будет составлять 2 * logn итераций в этих худших случаях.

Answer 5

Если вы собираетесь сделать это более одного раза, вы можете создать хеш-таблицу со значениями элемента в качестве ключа и индексом первого и последнего элемента в качестве значения.

Чтение данных для создания хеш-таблицы - это операция O (n), но затем поиск индексов близок к операции O (1).