දී ඇති පරාසය තුළ සමාන මූලද්‍රව්‍ය සහිත දර්ශක ගණන


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ග්‍රේ ඔරේන්ජ් ඇත්ත වශයෙන්ම ඔපෙරා Pinterest Snapdeal යාහූ
අරා විමසුම් ගැටළුව

ඔබට ලබා දී ඇත නිඛිල අරාව, 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 නොවේ නම්, එයින් අදහස් වන්නේ එය පළමු මූලද්‍රව්‍යය නොවේ නම් ගමන් කරන බවයි. ArrayDummy ධාරාවේ මූලද්‍රව්‍යයේ එකතුව සහ පෙර මූලද්‍රව්‍යය වත්මන් arrayDummy දර්ශකයට ගබඩා කරන්න.

ලබා දී ඇති සෑම විමසුමකටම පරාසයේ වම් දර්ශකය 0 ට සමාන නම්, අරාව ඩම්මි [දකුණ - 1] ආපසු දෙන්න. එය 0 නොවේ නම්, අරාව ඩම්මි [දකුණ - 1] සහ අරා ඩම්මි [වමේ - 1] අතර වෙනස නැවත ලබා දෙන්න.

කේතය

ගණනය කිරීම සඳහා C ++ කේතය දී ඇති පරාසය තුළ සමාන මූලද්‍රව්‍ය සහිත දර්ශක ගණන

#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) සෑම විමසුමකටම සහ සාමාන්ය (n) පෙර පරිගණක සඳහා.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. ArrayDummy නිර්මාණය කිරීම සඳහා මෙම අවකාශය අවශ්‍ය වේ.