Java код для подсчета в отсортированном ArrayList для определенного диапазона

Question

Необходимо найти количество элементов в отсортированном ArrayList из заданного диапазона (x, y). И счет должен иметь количество элементов диапазона также, если он находится в ArrayList.

Итак, я сделал это, обойдя весь список и получив счет.

Псевдо- код:

count = 0; 
for (i=0; i<length(list); i++)
{
if (list[i]>= startrange and list[i]<=endrange)
  {
    count = count+1;
  }
}

В настоящее время решение занимает больше времени, поскольку размер входного массива превышает 1000000. Помогите оптимизировать решение.

Пример:

Входной массив выглядит так [1,4,5,8,9,12,16,19,23,26,28,29,30,31,33,35,37].

Диапазон ввода: (12,30)

Вывод должен быть таким, как 8

Answer 1

Вы сказали Нужно найти количество элементов в отсортированном ArrayList из заданного диапазона (x, y) .

Таким образом, вы можете использовать binary search, чтобы сделать ваш код эффективным.

• В бинарном поиске у нас сначала есть 2 указателя, скажем low и high. Теперь мы начинаем наш поиск со среднего элемента в этом диапазоне. Если средний элемент меньше требуемого, мы переместимся в правую часть диапазона (mid + 1,high), иначе мы переместимся в левую часть диапазона (low,mid-1).

• В В этом конкретном случае мы должны выполнить 2 бинарных поиска. Давайте возьмем (12,30) в качестве примера. Один - найти самый низкий индекс с 12, а другой - двоичный поиск, чтобы найти самый высокий индекс с 30. Ответ на этот запрос будет highestIndex - lowestIndex + 1.

Фрагмент:

public class Main{
    public static void main(String[] args) {
        int[] arr = {1,4,5,8,9,12,16,19,23,26,28,29,30,31,33,35,37};
        int[][] queries = {
            {12,30},
            {-1,37},
            {1,49}
        };

        for(int[] q : queries){
            System.out.println(binarySearch(arr,q[0],q[1]));
        }
    }

    private static int binarySearch(int[] arr,int low,int high){
        return highestIndex(arr,high) - lowestIndex(arr,low) + 1; // + 1 because of 0-based indexing
    }

    private static int highestIndex(int[] arr,int num){
        int low = 0 , high = arr.length - 1;
        while(low <= high){
            int mid = low + (high - low) / 2; // (or (low + high)/2, as it doesn't matter in this context
            if(arr[mid] <= num) low = mid + 1;
            else high = mid - 1;
        }

        return high;
    }

    private static int lowestIndex(int[] arr,int num){
        int low = 0 , high = arr.length - 1;
        while(low <= high){
            int mid = low + (high - low) / 2; // (or (low + high)/2, as it doesn't matter in this context
            if(arr[mid] >= num) high = mid - 1;
            else low = mid + 1;
        }

        return low;
    }
}

Демонстрация: https://onlinegdb.com/BJ4g3AXXL

• Пробел Сложность кода выше O(1).
• Сложность времени кода выше O(Q * (log(N) + log(N))) ~ O(Q * 2 * log(N)) ~ O(Q * log(N)) асимптотически где Q - количество запросов, N - размер массива.

Answer 2

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

Answer 3

После Java 8 Потоковая однострочная работа будет работать нормально и вернет результат, как и ожидалось, без использования громоздкого for-l oop.

int[] xyz = { 1, 4, 5, 8, 9, 12, 16, 19, 23, 26, 28, 29, 30, 31, 33, 35, 37 };
long elementCountWithinRange = Arrays.stream(xyz).filter(x -> (x > 12 && x <= 31)).count();
    System.out.println(elementCountWithinRange); // will return 8

Примечание: Ранее аналогичный ответ, заданный @ Гаурав Дхиман , неверен, поскольку выражение не скомпилируется, так как метод count () возвращает long и не int. Кроме того, даже если вы решите, что это даст ошибку ниже:

The operator >= is undefined for the argument type(s) int[], int

Чтобы решить, что я использовал Arrays.stream() вместо Stream.of() для создания потока.

Answer 4

int cnt=Stream.of(arr).filter(o->(o>=12&& o<=30)).count();