ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಸಮಾನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಸೂಚಿಕೆಗಳ ಸಂಖ್ಯೆ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗ್ರೇ ಆರೆಂಜ್ ವಾಸ್ತವವಾಗಿ ಒಪೆರಾ pinterest ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ಯಾಹೂ
ಅರೇ ಪ್ರಶ್ನೆ ಸಮಸ್ಯೆ

ನಿಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ, q ಪ್ರಶ್ನೆಗಳು, ಮತ್ತು ಎಡ ಮತ್ತು ಬಲಕ್ಕೆ ಒಂದು ಶ್ರೇಣಿ. “ಕೊಟ್ಟಿರುವ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಸಮಾನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಸೂಚಿಕೆಗಳ ಸಂಖ್ಯೆ” <= i <ಬಲಕ್ಕೆ ಎಡಕ್ಕೆ ಹೋದ ರೀತಿಯಲ್ಲಿ ಪೂರ್ಣಾಂಕಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಹೇಳುತ್ತದೆi = ಎj + 1.

ಉದಾಹರಣೆ

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

ವಿವರಣೆ

ಪ್ರಶ್ನೆ 1 ಗಾಗಿ, ಅಲ್ಲಿ ಎಡ = 2, ಬಲ = 6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

ಎಣಿಕೆ 3 ಆಗಿದೆ.

ಪ್ರಶ್ನೆ 2 ಗಾಗಿ, ಅಲ್ಲಿ ಎಡ = 4, ಬಲ = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

ಎಣಿಕೆ 3 ಆಗಿದೆ.

ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಸಮಾನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಸೂಚಿಕೆಗಳ ಸಂಖ್ಯೆ

 

ಕ್ರಮಾವಳಿ

  1. ರಚನೆಯನ್ನು ರಚಿಸಿ.
  2. ರಚನೆಯ ಮೂಲಕ ಸಂಚರಿಸಿ.
  3. ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶವು ಮುಂದಿನ ಅಂಶಕ್ಕೆ ಸಮನಾಗಿದ್ದರೆ, ರಚಿಸಿದ ರಚನೆಯ ಅಂಶವು 1 ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂದು ಗುರುತಿಸಿ.
  4. ಸೂಚ್ಯಂಕವು 0 ಕ್ಕೆ ಸಮನಾಗಿರದಿದ್ದರೆ, ಅರೇಡಮ್ಮಿಯ ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶ ಮತ್ತು ಮುಂದಿನ ರಚನೆಯ ಅಂಶವನ್ನು ಅರೇ ಡಮ್ಮಿ [i] ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ.
  5. ಪ್ರಶ್ನೆಯನ್ನು ಪರಿಹರಿಸಿ, ಎಡ ಸ್ಥಾನವು 0 ಕ್ಕೆ ಸಮನಾಗಿದ್ದರೆ, ನಂತರ ಅರೇಡಮ್ಮಿ [ಬಲ -1] ಅನ್ನು ಹಿಂತಿರುಗಿ, ಇಲ್ಲದಿದ್ದರೆ ಅರೇ ಡಮ್ಮಿ [ಬಲ -1] ಮತ್ತು ಅರೇಡಮ್ಮಿ [ಎಡ -1] ವ್ಯತ್ಯಾಸವನ್ನು ಹಿಂತಿರುಗಿಸಿ.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಪೂರ್ಣಾಂಕ ರಚನೆ, ಮತ್ತು ಎಡಭಾಗ ಮತ್ತು ಬಲಭಾಗದ ವ್ಯಾಪ್ತಿ. ಪಕ್ಕದ ಅಂಶಗಳು ಒಂದಕ್ಕೊಂದು ಸಮನಾಗಿರುವ ರೀತಿಯಲ್ಲಿ ಸೂಚ್ಯಂಕಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಮ್ಮನ್ನು ಕೇಳಲಾಗುತ್ತದೆ. ಎರಡು ವಿಭಿನ್ನ ಸೂಚ್ಯಂಕಗಳೊಂದಿಗೆ ನಾವು ಎರಡು ಸಮಾನ ಪಕ್ಕದ ಅಂಶಗಳನ್ನು ಕಂಡುಕೊಂಡರೆ, 1 ಮತ್ತು ಹೀಗೆ ಎಣಿಸಿ. ನಂತರ ನಾವು ಗರಿಷ್ಠ ಗಾತ್ರದ ಶ್ರೇಣಿಯನ್ನು ರಚಿಸುತ್ತೇವೆ. ನಿರ್ದಿಷ್ಟ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವ ಸೂಚ್ಯಂಕವನ್ನು ಎಣಿಸುವ ಕಾರ್ಯವನ್ನು ನಾವು ರಚಿಸಿದ್ದೇವೆ. ಪಕ್ಕದ ಎರಡು ಅಂಶಗಳು ಒಂದಕ್ಕೊಂದು ಸಮಾನವಾಗಿರುತ್ತದೆ ಎಂಬುದು ಷರತ್ತು.

ನಾವು ರಚನೆಯ ಮೂಲಕ ಪ್ರಾರಂಭದಿಂದ ರಚನೆಯ ಉದ್ದಕ್ಕಿಂತ ಕಡಿಮೆ ಇರುವವರೆಗೆ ಚಲಿಸುತ್ತೇವೆ. ರಚನೆಯ ಪ್ರಸ್ತುತ ಅಂಶವು ರಚನೆಯ ಮುಂದಿನ ಅಂಶಕ್ಕೆ ಸಮಾನವಾಗಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಪರಿಸ್ಥಿತಿ ನಿಜವೆಂದು ಕಂಡುಬಂದಲ್ಲಿ. ನಂತರ ನಾವು ಆ ಮೌಲ್ಯವನ್ನು ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕದಲ್ಲಿ 1 ರಿಂದ 1 ಎಂದು ಗುರುತಿಸುತ್ತೇವೆ. ನಾವು ಇದನ್ನು 1 ಎಂದು ಗುರುತಿಸುತ್ತೇವೆ ಏಕೆಂದರೆ ಪಕ್ಕದ ಯಾವುದೇ ಅಂಶಗಳು ಸಮಾನವಾಗಿದೆಯೇ ಎಂದು ನಾವು ತಿಳಿದುಕೊಳ್ಳುತ್ತೇವೆ. ನಂತರ ಪ್ರತಿ ಜೋಡಿಯನ್ನು ಎಣಿಕೆ 2 ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಹಿಂದಿನ ಜೋಡಿಯ ಸಾಮಾನ್ಯವಾದ ಒಂದು ಅಂಶವನ್ನು ಹೊಂದಿರುವ ಮುಂದಿನ ಜೋಡಿಯನ್ನು 1 ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಮತ್ತು ಹೀಗೆ. N ಜೋಡಿಗಳು ಸಮಾನವಾಗಿದ್ದರೆ n-0 ಎಣಿಕೆ ಇರುತ್ತದೆ. ಸೂಚ್ಯಂಕ ಮೌಲ್ಯವು XNUMX ಅಲ್ಲದಿದ್ದರೆ ಅದು ಮೊದಲ ಅಂಶವಲ್ಲದಿದ್ದರೆ ಸಂಚರಿಸುವಾಗ ಇದರರ್ಥ. ಅರೇ ಡಮ್ಮಿ ಪ್ರವಾಹದ ಅಂಶ ಮತ್ತು ಹಿಂದಿನ ಅಂಶದ ಮೊತ್ತವನ್ನು ಪ್ರಸ್ತುತ ಅರೇಡಮ್ಮಿಯ ಸೂಚ್ಯಂಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ.

ಶ್ರೇಣಿಯ ಎಡ ಸೂಚ್ಯಂಕ 0 ಕ್ಕೆ ಸಮನಾಗಿದ್ದರೆ ನೀಡಲಾದ ಪ್ರತಿಯೊಂದು ಪ್ರಶ್ನೆಗೆ, ನಂತರ ಅರೇ ಡಮ್ಮಿ [ಬಲ - 1] ಅನ್ನು ಹಿಂತಿರುಗಿಸಿ. ಅದು 0 ಅಲ್ಲದಿದ್ದರೆ, ಅರೇ ಡಮ್ಮಿ [ಬಲ - 1] ಮತ್ತು ಅರೇ ಡಮ್ಮಿ [ಎಡ - 1] ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಹಿಂತಿರುಗಿಸಿ.

ಕೋಡ್

ಎಣಿಸಲು ಸಿ ++ ಕೋಡ್ ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಸಮಾನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಸೂಚಿಕೆಗಳ ಸಂಖ್ಯೆ

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

ಎಣಿಸಲು ಜಾವಾ ಕೋಡ್ ನಿರ್ದಿಷ್ಟ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಸಮಾನ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಸೂಚಿಕೆಗಳ ಸಂಖ್ಯೆ

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

 ಒ (1) ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ ಮತ್ತು ಓ (ಎನ್) ಪೂರ್ವ ಕಂಪ್ಯೂಟಿಂಗ್ಗಾಗಿ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಅರೇ ಡಮ್ಮಿ ಸೃಷ್ಟಿಗೆ ಈ ಸ್ಥಳದ ಅಗತ್ಯವಿದೆ.