Эффективно найти количество целых чисел в отсортированном массиве

Ответ 1

Измените свой двоичный поиск, чтобы найти первое и последнее вхождение данного ввода, тогда результат между этими двумя индексами будет результатом.

Чтобы найти первое и последнее вхождение с использованием двоичного поиска, вам нужно немного изменить бит из обычного алгоритма бинарного поиска. В двоичном поиске значение возвращается при совпадении. Но здесь, в отличие от обычного бинарного поиска, вам нужно продолжить поиск, пока не найдете несоответствие.

полезные ссылки

обнаружение последнего события, поиск первого события

Немного обновить

после того, как вы найдете первое вхождение, вы можете использовать этот индекс в качестве начальной точки следующего бинарного поиска, чтобы найти последний.

Ответ 2

Сделайте двойной поиск, чтобы найти первое вхождение. Сделайте двойной поиск, чтобы найти последнее вхождение. Число вхождений равно числу чисел между найденными двумя индексами.

Рабочий код:

public class Main {
    public static void main(String[] args){
        int[] arr = {-5, -5, 1, 1, 1, 1, 1, 1, 
                                    1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99};
        int lo = getFirst(arr, -5);
        if(lo==arr.length){ // the number is not present in the array.
            System.out.println(0);
        }else{
            int hi = getLast(arr, -5);
            System.out.println((hi-lo+1));
        }
    }

    // Returns last occurence of num or arr.length if it does not exists in arr.
    static int getLast(int[] arr, int num){
        int lo = 0, hi = arr.length-1, ans = arr.length;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(arr[mid]==num){
                ans = mid;
                lo = mid+1;
            }else if(arr[mid]<num){
                lo = mid+1;
            }else if(arr[mid]>num){
                hi = mid-1;
            }
        }
        return ans;
    }

    // Returns first occurence of num or arr.length if it does not exists in arr.
    static int getFirst(int[] arr, int num){
        int lo = 0, hi = arr.length-1, ans = arr.length;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(arr[mid]==num){
                ans = mid;
                hi = mid-1;
            }else if(arr[mid]<num){
                lo = mid+1;
            }else if(arr[mid]>num){
                hi = mid-1;
            }
        }
        return ans;
    }
}

Ответ 3

Приходят в голову два решения:

1) Сделайте двоичный поиск в порядке, но сохраните тот инвариант, который он обнаруживает первым. Затем выполните линейный поиск. Это будет Theta (log n + C), где C - счет.

Программирование Pearls от Jon Bentley имеет хорошую запись, где он упоминает, что поиск первого события действительно более эффективен, чем поиск любого события.

2) Вы также можете выполнить два бинарных поиска, один для первого вхождения и один для последнего, а также разницу между индексами. Это будет Theta (log n).

Вы можете решить, какое решение применить на основе ожидаемого значения C. Если C = o (log n) (да, малый o), то поиск первого появления и выполнение линейного поиска будет лучше. В противном случае выполните два бинарных поиска.

Если вы не знаете ожидаемого значения C, вам может быть лучше с решением 2.

Ответ 4

На самом деле есть немного лучшее решение, чем данные решения! Это комбинация двух разных способов выполнения двоичного поиска.

Сначала вы выполните двоичный поиск, чтобы получить первое событие. Это O (log n)

Теперь, начиная с первого индекса, который вы только что нашли, вы выполняете другой вид двоичного поиска: вы угадываете частоту этого элемента F, начиная с предположения F = 1 и удваивая свою оценку и проверяя, является ли элемент повторяется. Это гарантированно будет O (log F) (где F - частота).

Таким образом, алгоритм работает в O (log N + log F)

Вам не нужно беспокоиться о распределении чисел!

Ответ 5

IMHO это наиболее эффективное решение: другие, возможно, упоминали о подобном подходе, но я думаю, что это проще всего объяснить и проще всего понять, также имеет модификацию, которая ускорит процесс на практике:

В основном идея заключается в нахождении наименьшего и самого большого индекса вхождения. Наименьшее обнаружение O (log N) с использованием двоичного поиска (с использованием метода Ньютона для фактического увеличения производительности в среднем случае является возможным улучшением). Если вы не знаете, как изменить бинарный поиск, чтобы найти наименьший индекс, тривиальная модификация состоит в том, чтобы искать элемент со значением (p - 0.5) - очевидно, вы не найдете этого значения в массиве integer, но если бинарный поиск завершается индекс будет рядом с местом остановки рекурсии. Вам просто нужно проверить, существует ли он вообще. Это даст вам наименьший индекс.

Теперь, чтобы найти самый большой индекс, снова вам нужно будет запустить двоичный поиск, на этот раз используя наименьший индекс в качестве нижней границы и (p + 0.5) в качестве цели поиска, это гарантированно будет O (log N), в среднем случае это будет O (log N/2). Используя метод Ньютона и принимая во внимание значения верхней и нижней границ, на практике улучшите производительность.

Как только вы найдете самый большой и наименьший индекс, разница между ними, очевидно, является результатом.

Для равномерно распределенных чисел использование модификации Newton значительно улучшит время выполнения (в случае непрерывной равноудаленной последовательности чисел это будет O (1) (два или три шага), чтобы найти наименьшие и наибольшие значения), хотя теоретическая сложность по-прежнему равна O (log N) для произвольного ввода.