在給定範圍內的偶數或奇數概率查詢


難度級別
經常問 谷歌 霍尼韋爾 尤伯杯
排列

我們給了 排列 整數,q個查詢。 每個查詢包含三個整數,它們定義了一種查詢類型。 這意味著如果給定0,則意味著必須找到在給定範圍內選擇奇數的可能性。 範圍定義為起點和終點。 在此特定範圍內的任何類型的特定查詢。 您必須找到每個查詢的解決方案。 每個查詢將採用以下形式

TSE:如果給定T = 0,則意味著必須找到在給定數組A中給定範圍(S:起點,E:終點)中選擇偶數的可能性。

TSE:如果給定T = 1,則意味著必須找到在給定數組A中給定範圍(S:起點,E:終點)中選擇奇數的可能性。

輸入:

array [] = {2,3,4,5,6}

查詢1:1 1 3

查詢1:0 1 4

輸出:

1 / 3

1 / 2

說明:

我們在查詢中給定T = 1,這意味著我們必須找到選擇包含1和3的奇數的可能性。

我們在查詢中給定T = 0,這意味著我們必須找到選擇1和4(含)範圍內的偶數的可能性。

在給定範圍內的偶數或奇數概率查詢

算法

  1. 為奇數和偶數創建兩個數組,其大小與給定數組相同。 將兩個數組的第一個元素初始化為0。
  2. 遍歷數組並檢查數字是否為奇數,然後將我們創建的奇數數組的值填充為奇數[i] +1的數量,並填充到我們創建的偶數數組中,填充為偶數[i]的數量,如果找到了偶數,則相同,將奇數存儲到當前的奇數evenNumber數組中,並將奇數數組存儲到奇數數組中。
  3. 遍歷直到查詢次數,並存儲右,左和1的差。
  4. 檢查我們是否必須選擇偶數或奇數來找到概率,如果是奇數,則將值存儲在probab中作為奇數[right]和奇數[left – 1]之差。
  5. 否則,將值存儲在probab中,作為evenNumber [right]和evenNumber [left – 1]之差。
  6. 檢查概率是否小於或等於0,然後打印0。否則,等於1,然後打印XNUMX。否則,找到可以計算的優惠總數。
  7. 打印probab值和該收藏數量。

解釋

我們將創建兩個數組,一個用於存儲奇數,另一個用於存儲偶數。 現在,我們將遍歷數組,並確定數組元素是奇數還是偶數。 我們將把偶數存儲到奇數數組中。 和evenNumber的先前值到evenNumber的當前值一樣,如果數字為偶數,則要遵循相同的值。 然後將奇數值存儲到evenNumber數組,並將奇數數組的先前值存儲到當前奇數的當前值。 所有這些都是在創建的數組中分別用數字創建和填充數組。

獲取查詢的類型,將左,右點作為範圍,獲取它們之間的差。 我們將發現給定的查詢是哪種類型。 如果它大於1,那麼我們必須選擇一個奇數以找出選擇偶數的可能性。 否則,我們將找到一個範圍內偶數的概率。 如果它是奇數,那麼我們將獲得我們創建的奇數數組的差,並且與偶數概率相同,即偶數的差。 我們將差異存儲在probab中,如果probab小於或等於0,我們將打印0,否則,如果probab等於k,則打印1。 最後,打印出價值概率和優勢。

履行

C ++程序,用於查詢給定範圍內的偶數或奇數概率

#include<iostream>

using namespace std;

#define C 3

int getDivisor(int a, int b)
{
    if (a == 0 || b == 0)
        return 0;

    if (a == b)
        return a;

    if (a > b)
        return getDivisor(a - b, b);

    return getDivisor(a, b - a);
}

void solveQuery(int arr[], int n, int Q,int query[][C])
{
    int evenNumber[n + 1];
    int oddNumber[n + 1];
    evenNumber[0] = oddNumber[0] = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] & 1)
        {
            oddNumber[i + 1] = oddNumber[i] + 1;
            evenNumber[i + 1] = evenNumber[i];
        }
        else
        {
            evenNumber[i + 1] = evenNumber[i] + 1;
            oddNumber[i + 1] = oddNumber[i];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int right = query[i][2];
        int left = query[i][1];
        int T = query[i][0];

        int dif = right - left + 1;
        int probab;

        if (T)
            probab = oddNumber[right] - oddNumber[left - 1];
        else
            probab = evenNumber[right] - evenNumber[left - 1];

        if (!probab)
            cout << "0" << endl;

        else if (probab == dif)
            cout << "1" << endl;

        else
        {
            int div = getDivisor(probab, dif);
            cout << probab / div << "/" << dif / div << endl;
        }
    }
}

int main()
{
    int arr[] = { 2,3,4,5,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2;
    int query[Q][C] = { { 1, 1, 3 },
        { 0, 1, 4 }
    };

    solveQuery(arr, n, Q, query);
    return 0;
}
1/3
1/2

給定範圍內的偶數或奇數概率查詢的Java程序

public class QueryProbability
{
    static int getDivisor(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return getDivisor(a - b, b);

        return getDivisor(a, b - a);
    }
    
    static void solveQuery(int []arr, int n, int Q, int [][]query)
    {
        int []evenNumber = new int[n + 1];
        int []oddNumber = new int[n + 1];
        evenNumber[0] = oddNumber[0] = 0;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) > 0)
            {
                oddNumber[i + 1] = oddNumber[i] + 1;
                evenNumber[i + 1] = evenNumber[i];
            }
            else
            {
                evenNumber[i + 1] = evenNumber[i] + 1;
                oddNumber[i + 1] = oddNumber[i];
            }
        }
        
        for (int i = 0; i < Q; i++)
        {
            int right = query[i][2];
            int left = query[i][1];
            int T = query[i][0];

            int dif = right - left + 1;
            int probab;
            if (T > 0)
                probab = oddNumber[right] - oddNumber[left - 1];
            else
                probab = evenNumber[right] - evenNumber[left - 1];

            if (probab <= 0)
                System.out.println("0");
            else if (probab == dif)
                System.out.println("1");

            else
            {
                int div = getDivisor(probab, dif);
                System.out.println(probab / div + "/" +dif / div);
            }
        }
    }
    
    static public void main (String[] args)
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        int Q = 2;
        int [][]query = { { 1, 1, 3 },
            { 0, 1, 4 }
        };

        solveQuery(arr, n, Q, query);
    }
}
1/3
1/2

給定範圍內偶數或奇數概率查詢的複雜度分析

時間複雜度

O(q * n) 哪裡 “Q” 是查詢數量, “ n” 是數組中元素的數量

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。

參考文獻