തന്നിരിക്കുന്ന ശ്രേണിയിലെ മൂല്യങ്ങളുള്ള അറേ ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള അന്വേഷണങ്ങൾ


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു Coursera ഡി.ഇ.ഷാ ഗൂഗിൾ പേ സ്നാപ്ഡേൽ ടൈംസ് ഇന്റർനെറ്റ് യാഹൂ
അറേ ബിറ്റുകൾ അന്വേഷണ പ്രശ്നം

പ്രശ്നം പ്രസ്താവന

“തന്നിരിക്കുന്ന ശ്രേണിയിലെ മൂല്യങ്ങളുള്ള അറേ ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള അന്വേഷണങ്ങൾ” എന്ന പ്രശ്‌നം നിങ്ങൾക്ക് ഒരു ഉണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി x, y എന്നീ രണ്ട് സംഖ്യകളും. തന്നിരിക്കുന്ന x നും y നും ഇടയിലുള്ള അറേയിലുള്ള അക്കങ്ങളുടെ എണ്ണം കണ്ടെത്താൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം

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

വിശദീകരണം

കാരണം, ഒരു അറേയിൽ 4 ഘടകങ്ങൾ ഉണ്ട്, അതായത് 2, 4, 6, 8 എന്നിവ 2 നും 8 നും ഇടയിൽ കിടക്കുന്നു.

തന്നിരിക്കുന്ന ശ്രേണിയിലെ മൂല്യങ്ങളുള്ള അറേ ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള അന്വേഷണങ്ങൾ

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

വിശദീകരണം

3, 6, 8 എന്നിങ്ങനെയുള്ള 10 ഘടകങ്ങൾ ഒരു അറേയിൽ ഉണ്ട്, അവ 5 നും 10 നും ഇടയിൽ ഉൾക്കൊള്ളുന്നു.

അൽഗോരിതം

  1. അടുക്കുക ശ്രേണി.
  2. ബൈനറി തിരയൽ ഉപയോഗിച്ച് y മൂലകത്തിന്റെ അറേയുടെ വലിയ സൂചിക കണ്ടെത്തുക, വലിയ സൂചിക നൽകുക.
  3. ബൈനറി തിരയൽ ഉപയോഗിച്ച് x മൂലകത്തിന്റെ അറേയുടെ ചെറിയ സൂചിക കണ്ടെത്തുക, ചെറിയ സൂചിക നൽകുക.
  4. വലിയ സൂചികയും ചെറിയ സൂചികയും പ്ലസ് 1 ഉം തമ്മിലുള്ള വ്യത്യാസം നൽകുക.

വിശദീകരണം

ഞങ്ങൾ ഒരു പൂർണ്ണസംഖ്യയും x, y എന്നീ രണ്ട് അക്കങ്ങളും നൽകി. തന്നിരിക്കുന്ന x നും y നും ഇടയിലുള്ള ഒരു നിശ്ചിത അറേയിലെ ആകെ സംഖ്യകൾ കണ്ടെത്താൻ ഞങ്ങൾ ആവശ്യപ്പെട്ടു. അടിസ്ഥാനപരമായി, “x” നേക്കാൾ വലിയ സംഖ്യകളുടെ എണ്ണം നാം കണ്ടെത്തണം. “Y” നേക്കാൾ ചെറു സംഖ്യകളുടെ എണ്ണം. ഞങ്ങൾ ശ്രേണി തരംതിരിക്കും. അതിനു പിന്നിലെ കാരണം ഞങ്ങൾ ഒരു ബൈനറി തിരയൽ രീതി ഉപയോഗിക്കാൻ പോകുന്നു എന്നതാണ്. അതും പരിഷ്‌ക്കരിക്കുന്നു.

നമ്പറിന്റെ സൂചിക നേടുക y ബൈനറി തിരയൽ ഉപയോഗിച്ച് അറേയിൽ. ബൈനറി തിരയലിൽ, y ഉള്ള സൂചിക കണ്ടെത്താൻ ഞങ്ങൾ ശ്രമിക്കുന്നു. താഴ്ന്ന മൂല്യം ഉയർന്ന മൂല്യത്തേക്കാൾ കുറവോ തുല്യമോ ആകുന്നതുവരെ ഞങ്ങൾ ലൂപ്പ് തുടരുന്നു. സാധാരണയായി 0-ാമത്തെ സൂചികയും ഉയർന്നത് അറേയുടെ അവസാന സൂചികയുമാണ്, കാരണം ഞങ്ങൾ അറേ സൂചികകളിൽ ഒരു ബൈനറി തിരയൽ നടത്തുന്നു. ഓരോ ചോദ്യത്തിനും ലോഗരിഥമിക് സമയ സങ്കീർണ്ണതയിൽ നൽകിയിരിക്കുന്ന ശ്രേണിയിലെ മൂല്യങ്ങളുള്ള അറേ ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള ചോദ്യങ്ങൾക്ക് ഉത്തരം നൽകാൻ ബൈനറി തിരയൽ ഞങ്ങളെ അനുവദിക്കുന്നു.

കുറഞ്ഞതും ഉയർന്നതുമായ മൂല്യത്തിന്റെ മധ്യഭാഗം നമുക്ക് ലഭിക്കും, കൂടാതെ അറേ [മിഡ്] ലെ മൂലകം x ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക. ഇത് ശരിയാണെങ്കിൽ, ഉയർന്ന മൂല്യം മിഡ് -1 ലേക്ക് അപ്‌ഡേറ്റ് ചെയ്യുക. കുറഞ്ഞതിന്റെ മൂല്യം + 1 മുതൽ മധ്യഭാഗം വരെ അപ്‌ഡേറ്റുചെയ്യുക. Y എന്ന മൂലകത്തിലും ഇത് പ്രയോഗിക്കണം. അങ്ങനെയാണെങ്കിൽ‌, ഞങ്ങൾ‌ കൂടുതൽ‌ സൂചിക കണ്ടെത്തും, കൂടാതെ അറേ [മിഡ്] പരിശോധിക്കുന്നതിനുപകരം y ന് തുല്യമാണ്. അറേ [മിഡ്] y യ്ക്ക് തുല്യമാണോയെന്ന് പരിശോധിച്ചുകൊണ്ടിരിക്കുക, കുറഞ്ഞ മൂല്യം മുതൽ മിഡ് + 1 വരെയും ഉയർന്ന മൂല്യം 1 മുതൽ മിഡ് XNUMX വരെയും അപ്‌ഡേറ്റ് ചെയ്യുക.

രണ്ട് സൂചികകളും വലുതും ചെറുതുമായി നേടുക, അവയുടെ വ്യത്യാസം മടക്കി അതിൽ 1 ചേർക്കുക. ഇത് ഞങ്ങൾക്ക് ആവശ്യമായ ഉത്തരമായിരിക്കും. തന്നിരിക്കുന്ന ശ്രേണിയിലെ മൂല്യങ്ങളുള്ള അറേ ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള ചോദ്യങ്ങൾക്ക് ഉത്തരം നൽകാൻ ഞങ്ങൾ ആഗ്രഹിച്ചുവെന്നത് ഓർക്കുക.

കോഡ്

ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ അറേ ഘടകങ്ങളുടെ എണ്ണം കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#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

ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ അറേ ഘടകങ്ങളുടെ എണ്ണം കണ്ടെത്താനുള്ള ജാവ പ്രോഗ്രാം

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 (ലോഗ് n) അറേ അടുക്കുന്നതിന് ഒരിക്കൽ ആയിരിക്കും O (n ലോഗ് n).

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. അറേ തരംതിരിക്കുമ്പോഴുള്ള സ്ഥലമാണ് ഞങ്ങൾ പരിഗണിച്ച ഇടം. ഇൻപുട്ട് സംഭരിക്കുന്നതിന് ആവശ്യമായ ഇടം “തന്നിരിക്കുന്ന ശ്രേണിയിലെ മൂല്യങ്ങളുള്ള അറേ ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള അന്വേഷണങ്ങൾ” പ്രശ്‌നത്തിൽ പരിഗണിക്കില്ല.