給定子數組中小於或等於給定數目的元素數  


難度級別
經常問 編碼國家 谷歌 Opera 瀏灠器 貝寶 Pinterest
排列

問題陳述  

問題“給定子數組中的元素數小於或等於給定數”表示給了您一個整數數組和q個查詢。 查詢將分為兩種:

  • queryUpdate(i,v):將有兩個整數i和v,以便更新array [i] = v。
  • queryPrint(left,right,k):打印小於等於k的範圍內的整數數量。

例  

arr[]={2, 4, 6, 1, 5)
queryPrint(0, 2, 2)
queryUpdate(2, 8)
queryPrint(1, 3, 5)
queryUpdate(4, 3)
queryUpdate(1, 3)
queryPrint(1, 2, 4)
1 2 1

解釋

queryPrint(0,2,2)將打印從索引2到0小於或等於2的元素數量,即1

queryUpdate(2,8)將使用值2更新索引8處的元素,即arr將為{2,4,8,1,5,XNUMX}

queryPrint(1,3,5)將打印從索引5到1小於或等於3的元素數量,即2

queryUpdate(4,3)將使用4更新索引3的元素,即arr為{2,4,8,1,3}

queryUpdate(1,3)將使用1更新索引3的元素,即arr為{2,3,8,1,3}

queryPrint(1,2,4)將打印從索引4到1小於或等於2的元素數量,即1

給定子數組中小於或等於給定數目的元素數

 

在子數組中查找小於等於給定值的數字的算法  

  1. 劃分 排列 分成大小等於n的平方根的塊,其中n是輸入數組的大小。
  2. 構建一個二進制索引樹,其大小比特定塊中數組中存在的最大元素大一號。
  3. 找出該數組所屬的每個元素的塊,並使用arr [i]處的1更新該塊的BIT數組。
  4. 對於每個更新查詢。 相對於索引為-1的數組原始值處的塊,更新BIT數組的值。
  5. 在特定索引的新元素處使用值1更新同一塊的BIT數組。
  6. 對於每個打印查詢。 查詢BIT數組,以計算小於或等於k的元素值。 對於完整塊還是不完整或部分塊,遍歷所有元素。
也可以看看
數組中給定索引範圍的GCD

解釋

我們給了一個整數數組和兩種查詢類型。 一種查詢是更新給定特定索引處的值。 另一個查詢是獲取小於等於k的元素數。 對於更新查詢,我們將獲得一個索引和一個值。 我們將更新值 v 在array [i]的給定索引處。 對於打印查詢或計數查詢,我們需要打印小於或等於k的整數數量。

我們將把數組分成幾個塊。 這些塊的大小將為數組長度的平方根。 對於每個街區,我們將保持 二叉索引樹。 對於數組元素的特定塊,二進制索引樹的大小將比最大元素大一倍。 由於每個塊都有BIT數組,因此請在array [i]的每個位置將值位數組更新為1,並找出該數組所屬的每個元素的塊,並按照與上述相同的步驟進行操作將arr [i]處的該塊的位數組更新為1。

對於每個更新查詢,更新BIT數組。 由於每個數組元素都有一個塊。 在特定索引處使用值-1更新該數組的值,並在給定索引處將該數組的新元素處的所需塊的BIT數組更新為值1。 對於打印查詢或計數值,只需遍歷循環即可。 對於完整塊或部分完整塊,將有兩種情況。 最後返回值。

也可以看看
最大二叉樹

推薦碼  

用於查找數字<=子數組中給定值的C ++代碼

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>

using namespace std;

const int MAX = 10001;

void update(int index, int block, int val, int bit[][MAX])
{
    for (; index < MAX ; index += (index&-index))
        bit[block][index] += val;
}
int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][MAX])
{
    int sum = 0;
    while (left<right && left%blockSize!=0 && left!=0)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }

    while (left + blockSize <= right)
    {
        int index = k;
        for (; index > 0 ; index -= index&-index)
            sum += bit[left/blockSize][index];
        left += blockSize;
    }

    while (left <= right)
    {
        if (arr[left] <= k)
            sum++;
        left++;
    }
    return sum;
}
void preprocess(int arr[], int blockSize, int n, int bit[][MAX])
{
    for (int i=0; i<n; i++)
        update(arr[i], i/blockSize, 1, bit);
}

void queryUpdate(int i, int v, int blockSize,int arr[], int bit[][MAX])
{
    update(arr[i], i/blockSize, -1, bit);
    update(v, i/blockSize, 1, bit);
    arr[i] = v;
}
int main()
{
    int arr[] = {2,4,6,1,5};
    int n = sizeof(arr)/sizeof(arr[0]);

    int blockSize = sqrt(n);

    int bit[blockSize+1][MAX];

    memset(bit, 0, sizeof(bit));

    preprocess(arr, blockSize, n, bit);

    cout << queryPrint (0, 2, 2, arr, blockSize, bit) << endl;

    queryUpdate(2, 8, blockSize, arr, bit);

    cout << queryPrint(1, 3, 5, arr, blockSize, bit) << endl;

    queryUpdate(4, 3, blockSize, arr, bit);

    queryUpdate(1, 3, blockSize, arr, bit);

    cout << queryPrint (1, 2, 4, arr, blockSize, bit) << endl;
    return 0;
}
1
2
1

用於查找數字<=子數組中給定值的Java代碼

class NumberElements
{
    static final int MAX = 10001;

    static void update(int index, int block, int val, int bit[][])
    {
        for ( ; index < MAX ; index += (index&-index))
            bit[block][index] += val;
    }
    static int queryPrint(int left, int right, int k, int arr[], int blockSize, int bit[][])
    {
        int sum = 0;
        while (left < right && left % blockSize != 0 && left != 0)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        while (left + blockSize <= right)
        {
            int index = k;
            for (; index > 0 ; index -= index&-index)
                sum += bit[left/blockSize][index];
            left += blockSize;
        }
        while (left <= right)
        {
            if (arr[left] <= k)
                sum++;
            left++;
        }
        return sum;
    }
    static void buildArray(int arr[], int blockSize, int n, int bit[][])
    {
        for (int i=0; i<n; i++)
            update(arr[i], i/blockSize, 1, bit);
    }

    static void queryUpdate(int i, int v, int blockSize, int arr[], int bit[][])
    {
        update(arr[i], i/blockSize, -1, bit);
        update(v, i/blockSize, 1, bit);
        arr[i] = v;
    }

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

        int blockSize = (int) Math.sqrt(arr.length);

        int bit[][] = new int[blockSize+1][MAX];
        buildArray(arr, blockSize, arr.length, bit);

        System.out.println(queryPrint(0, 2, 2, arr, blockSize, bit));

        queryUpdate(2, 8, blockSize, arr, bit);

        System.out.println(queryPrint(1, 3, 5, arr, blockSize, bit));

        queryUpdate(4, 3, blockSize, arr, bit);

        queryUpdate(1, 3, blockSize, arr, bit);

        System.out.println(queryPrint (1, 2, 4, arr, blockSize, bit));

    }
}
1
2
1

複雜度分析  

時間複雜度

O(1) 用於更新數組和 O(N) 用於打印陣列。

也可以看看
在二叉樹中刪除

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 問題“給定子數組中的元素數小於或等於給定數”具有線性空間。