查詢值在給定範圍內的數組元素的計數  


難度級別
經常問 Coursera 谷歌 PayU Snapdeal 時代互聯網 雅虎
排列 查詢問題

問題陳述  

問題“查詢具有給定範圍內的值的數組元素的數量”表明您有一個 整數 排列 還有兩個數字x和y。 問題陳述要求找出位於給定x和y之間的數組中存在的數字計數。

例  

arr[]={2,4,6,8,1,10}
x = 2, y = 8
4

解釋

因為數組中存在4個元素,所以2、4、6和8位於2和8之間(包括XNUMX和XNUMX)。

查詢值在給定範圍內的數組元素的計數

arr[]={2,4,6,8,1,10}
x = 5, y = 10
3

解釋

因為數組中存在3個元素,分別是6、8和10,所以位於5和10之間(包括XNUMX和XNUMX)。

算法  

  1. 分類 數組。
  2. 通過使用二進制搜索找出元素y數組的較大索引,並返回較大索引。
  3. 通過使用二進制搜索找出元素x數組的較小索引,並返回較小的索引。
  4. 返回較大索引與較小索引之間的差加上1。

解釋  

我們給出了一個整數數組和兩個數字x和y。 我們已要求找出位於給定x和y之間的給定數組中存在的總數。 基本上,我們必須找到大於“ x”的數字計數。 且計數小於“ y”。 我們將對數組進行排序。 其背後的原因是我們將使用二進制搜索方法。 這也正在被修改。

也可以看看
刪除最小數量的元素,以便兩個數組中都不存在公共元素

獲取數字的索引 y 通過使用二進制搜索在數組中查找。 在二分查找中,我們嘗試找到存在y的索引。 我們繼續循環,直到low的值小於或等於high的值。 通常低是第0個索引,高是數組的最後一個索引,因為我們正在對數組索引進行二進制搜索。 使用二進制搜索使我們能夠對每個查詢的對數時間複雜度中給定範圍內的值的數組元素計數進行查詢。

我們將獲得低值和高值的中間值,並檢查array [mid]處的元素是否大於等於x。 如果是這樣,則將high的值更新為mid-1。 否則將low的值更新為中+1。 元素y也應如此。 但是在那種情況下,我們將找到更大的索引,而不是檢查array [mid]大於等於y。 然後繼續檢查array [mid]是否小於y,並將low的值更新為mid + 1,並將high的值更新為mid-1。

獲取兩個索引的更大和更小,然後返回它們的差並將其加1。 這將是我們要求的答案,該答案將返回。 記住,我們要回答查詢具有給定範圍內的值的數組元素的數量的查詢。

推薦碼  

C ++代碼查找給定範圍內的數組元素數

#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int greaterElement(int arr[], int n, int y)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] <= y)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
int countInRange(int arr[], int n, int x, int y)
{
    int count = 0;
    count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
    return count;
}
int main()
{
    int arr[] = {2,4,6,8,1,10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    int i = 2, j = 8;
    cout << countInRange(arr, n, i, j) << endl;

    i = 5, j = 10;
    cout << countInRange(arr, n, i, j) << endl;
    return 0;
}
4
3

Java程序查找給定範圍內的數組元素數

import java.io.*;
import java.util.Arrays;

class NumberOfElements
{
    private static int countInRange(int arr[], int n, int x, int y)
    {
        int count = 0;
        count = greaterElement(arr, n, y) -
                smallerElement(arr, n, x) + 1;
        return count;
    }
    
    private static int smallerElement(int arr[], int n, int x)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private static int greaterElement(int arr[], int n, int y)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] <= y)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }

    public static void main (String[] args)
    {
        int arr[] = {2,4,6,8,1,10 };
        int n = arr.length;

        Arrays.sort(arr);

        int x = 2, y = 8;
        System.out.println( countInRange(arr, n, x, y)); ;

        x = 5;
        y = 10;
        System.out.println( countInRange(arr, n, x, y));
    }
}
4
3

複雜度分析  

時間複雜度

運行每個查詢的時間為 O(log n) 並且對數組進行一次排序將是 O(n log n).

也可以看看
如何檢查兩個給定的集合是否不相交?

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 我們考慮的空間是由於對數組進行排序時所佔用的空間。 “在給定範圍內的值的數組元素的計數查詢”問題中未考慮存儲輸入所需的空間。