റീഡ് ഒൺലി അറേയിൽ ആവർത്തിച്ചുള്ള ഒന്നിലധികം ഘടകങ്ങളിൽ ഒന്ന് കണ്ടെത്തുക


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ക്യാപിറ്റൽ വൺ ഫേസ്ബുക്ക് ഗൂഗിൾ തീർച്ചയായും മൈക്രോസോഫ്റ്റ് പോസ്റ്റ്
അറേ ഹാഷ്

“വായിക്കാൻ മാത്രമുള്ള അറേയിൽ ആവർത്തിച്ചുള്ള ഒന്നിലധികം ഘടകങ്ങളിൽ ഏതെങ്കിലും ഒന്ന് കണ്ടെത്തുക” എന്ന പ്രശ്നം, നിങ്ങൾക്ക് വായന-മാത്രം നൽകിയിട്ടുണ്ടെന്ന് കരുതുക ശ്രേണി വലുപ്പത്തിന്റെ (n + 1). 1 മുതൽ n വരെയുള്ള സംഖ്യകൾ ഒരു അറേയിൽ അടങ്ങിയിരിക്കുന്നു. വായിക്കാൻ മാത്രമുള്ള അറേയിലെ ആവർത്തിച്ചുള്ള ഏതെങ്കിലും ഘടകങ്ങൾ കണ്ടെത്തുക എന്നതാണ് നിങ്ങളുടെ ചുമതല.

ഉദാഹരണം

റീഡ് ഒൺലി അറേയിൽ ആവർത്തിച്ചുള്ള ഒന്നിലധികം ഘടകങ്ങളിൽ ഒന്ന് കണ്ടെത്തുക

n = 5
arr[] = [1,2,4,2,3,5]
2

വിശദീകരണം

വായന-മാത്രം അറേയിലെ ആവർത്തിച്ചുള്ള ഒരേയൊരു ഘടകമാണിത്.

n = 9
arr[] = [1,2,4,6,3,5,7,8,9,9]
9

വിശദീകരണം

വായന-മാത്രം അറേയിലെ ആവർത്തിച്ചുള്ള ഒരേയൊരു ഘടകമാണിത്.

അൽഗോരിതം

  1. ഗണം “സ്ക്വയർറൂട്ട്” sqrt (n) ലേക്ക്.
  2. ശ്രേണി (n / squareroot) + 1 ആയി സജ്ജമാക്കുക.
  3. ഒരു വലുപ്പ ശ്രേണിയുടെ ഒരു നിര സൃഷ്ടിക്കുക.
  4. ഇതുപയോഗിച്ച് ഓരോ ഘടകത്തിന്റെയും ആവൃത്തി എണ്ണുക, സംഭരിക്കുക (freqCount [(arr [i] - 1) / squareroot] ++).
  5. ഗണം “കറന്റ്ബ്ലോക്ക്” ശ്രേണി -1 ലേക്ക്.
  6. ഞാൻ <ശ്രേണി -1 ആയിരിക്കുമ്പോൾ.
    1. FreqCount [i]> സ്ക്വയർറൂട്ട് ആണെങ്കിൽ, currentBlock = i ചെയ്ത് തകർക്കുക.
  7. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം.
  8. ഉൾപ്പെടുന്ന ഘടകങ്ങൾ പരിശോധിക്കാൻ ഒരു മാപ്പിൽ സഞ്ചരിക്കുക “കറന്റ്ബ്ലോക്ക്”.
    1. അതിനുശേഷം arr [i] ഇടുക, മാപ്പിന്റെ കീയുടെ മൂല്യത്തിന്റെ മൂല്യം വർദ്ധിപ്പിക്കുക.
    2. ഒരു കീയുടെ മൂല്യം 1 ൽ കൂടുതലാണെന്ന് കണ്ടെത്തിയാൽ arr [i] നൽകുക.
  9. മറ്റ് റിട്ടേൺ -1 (ഘടകങ്ങളൊന്നും കണ്ടെത്തിയില്ല).

വിശദീകരണം

ഒരു ശ്രേണിയിൽ‌ ആവർത്തിച്ചുള്ള മൂലകം കണ്ടെത്തുന്നതിന് ഞങ്ങൾ‌ ഒരു ചോദ്യം നൽ‌കി, അതിൽ‌ എല്ലാ സംഖ്യകളും 1 മുതൽ n വരെയും ഒരു അറേയുടെ വലുപ്പം n + 1 വരെയുമാണ്. ആവർത്തിച്ചുള്ള ഒരു മൂലകത്തിന്റെ സാന്നിധ്യം ഇത് കാണിക്കുന്നതിനാൽ അതിനുള്ള വലുപ്പം n + 1 ആണ്.

ഒരു ഹാഷ്‌മാപ്പ് സൃഷ്‌ടിച്ച് ഓരോ ഘടകങ്ങളുടെയും ആവൃത്തി എണ്ണം നിലനിർത്തുക എന്നതാണ് ഒരു ലളിതമായ പരിഹാരം. എന്നാൽ ഈ പരിഹാരത്തിന് O (N) സമയവും O (N) സ്ഥലവും ആവശ്യമാണ്. ഇതിനേക്കാൾ മികച്ചത് നമുക്ക് ചെയ്യാൻ കഴിയുമോ?

സ്‌ക്വയർ റൂട്ട് വിഘടനത്തിന് സമാനമായ ഒരു സമീപനം നമുക്ക് ഉപയോഗിക്കാം. ഈ സമീപനം നമ്മുടെ സ്ഥല സങ്കീർണ്ണതയെ O (sqrt (N)) ലേക്ക് കുറയ്ക്കും. Sqrt (N) + 1 വലുപ്പത്തിന്റെ ഒരു ശ്രേണി ഞങ്ങൾ സൃഷ്ടിക്കുന്നു. കൂടാതെ ar (i-1) / sqrt (n) സമവാക്യം അനുസരിച്ച് മൂല്യങ്ങൾക്ക് അനുയോജ്യമായ സൂചികകൾ വർദ്ധിപ്പിക്കുക. ഇത് ചെയ്തുകഴിഞ്ഞാൽ, ചതുരശ്ര (N) നേക്കാൾ വലിയ ആവൃത്തിയിലുള്ള ഒരു സൂചിക ഞങ്ങൾ തീർച്ചയായും കണ്ടെത്തും. ഇപ്പോൾ ഞങ്ങൾ മുമ്പത്തെ രീതി ഉപയോഗിക്കും, പക്ഷേ ഈ ശ്രേണിയിലെ ഘടകങ്ങൾക്ക് മാത്രം.

ഹാഷിംഗ് കൂടാതെ ചില അടിസ്ഥാന ഗണിതശാസ്ത്രവും പ്രശ്ന പരിഹാരത്തിനായി ഉപയോഗിക്കുന്നു. ആവർത്തിച്ചുള്ള ഘടകം കണ്ടെത്തുന്നതിന് ഞങ്ങൾ ഒരു അറേയും പാസ് അറേയുടെ വലുപ്പത്തേക്കാൾ 1 കുറവും നൽകും. ഇത് പരിഹരിക്കുന്നതിന് ഒരു ഉദാഹരണം നോക്കാം:

അറേ [] = {6, 1, 2, 3, 5, 4, 6}, n = 6

വലുപ്പം ആണെങ്കിൽ n + 1 അപ്പോൾ ഞങ്ങൾ കടന്നുപോകും n അതിലേക്ക്. ഇതിന്റെ വർ‌ഗ്ഗമൂലം കണ്ടെത്തേണ്ടതുണ്ട് n എന്നിട്ട് ചില വേരിയബിളുകളിൽ ഇത് സംഭരിക്കുക സ്ക്വയർറൂട്ട്= 2. ഇപ്പോൾ നമ്മൾ അറേയുടെ ശ്രേണി കണ്ടെത്തണം. ഞങ്ങൾ ഒരു അറേ പറയാൻ പോകുന്നു freqCount 'range = 4' വലുപ്പത്തിന്റെ, (n / squareroot) + 1 പ്രകാരം ഞങ്ങൾ ശ്രേണി കണ്ടെത്തും.

ഓരോ ഘടകത്തിന്റെയും ആവൃത്തികൾ ഞങ്ങൾ സഞ്ചരിച്ചുകൊണ്ട് സൃഷ്ടിച്ച ശ്രേണിയുടെ പരിധിക്കുള്ളിൽ കണക്കാക്കും. ഓരോ തവണ സഞ്ചരിക്കുമ്പോഴും ഞങ്ങൾ ഫ്രീക ount ണ്ട് [(arr (i) -1) / squareroot] ++ പിന്തുടരും.

ഞങ്ങളുടെ ഫ്രീ‌ക ount ണ്ട് അറേയിൽ‌ ഇനിപ്പറയുന്ന മൂല്യങ്ങൾ‌ ഉണ്ടായിരിക്കും.

freqCount: [2,2,3,0]

തയ്യാറാക്കുന്നു കറന്റ്ബ്ലോക്ക് ശ്രേണി -1 ലേക്ക് 3 ആണ്. ഞങ്ങൾ സഞ്ചരിക്കും freqCount അറേ. എന്നതിനേക്കാൾ വലുത് ഞങ്ങൾ കണ്ടെത്തിയാൽ സ്ക്വയർറൂട്ട് ശ്രേണിയിൽ. ഫ്രീക് ക ount ണ്ടിന്റെ രണ്ടാം സൂചികയിൽ‌ ഞങ്ങൾ‌ കണ്ടെത്തി കറൻറ്ബ്ലോക്ക് i ലേക്ക് സജ്ജമാക്കി ബ്രേക്ക്‌ ചെയ്യുക. ഞങ്ങൾ ഒരു പ്രഖ്യാപിക്കും ഹാഷ്‌മാപ്പ് ഇൻ‌പുട്ട് അറേയിലെ ഓരോ ഘടകങ്ങളും സഞ്ചരിച്ച് ഏതെങ്കിലും മൂലകം നിലവിലെ ബ്ലോക്കിനും സ്ക്വാററൂട്ടിനും അവകാശപ്പെട്ടതാണോയെന്ന് പരിശോധിക്കുക, അതെ എങ്കിൽ ഞങ്ങൾ അത് ഒരു മാപ്പിൽ ഇടുകയും ആ മൂല്യം [i] തിരികെ നൽകുകയും ചെയ്യും.

ഞങ്ങളുടെ output ട്ട്‌പുട്ട് ഇതായിരിക്കും: 6

വായിക്കാൻ മാത്രമുള്ള അറേയിലെ ഒന്നിലധികം ആവർത്തിക്കുന്ന ഘടകങ്ങളിൽ ഒന്ന് കണ്ടെത്താനുള്ള സി ++ കോഡ്

#include <unordered_map>
#include<iostream>
#include<math.h>
using namespace std;

int getRepeatedNumber(int arr[], int len)
{
    int squareroot = sqrt(len);
    int range = (len / squareroot) + 1;
    int count[range] = {0};

    for (int i = 0; i <= len; i++)
    {
        count[(arr[i] - 1) / squareroot]++;
    }
    int currentBlock = range - 1;
    for (int i = 0; i < range - 1; i++)
    {
        if (count[i] > squareroot)
        {
            currentBlock = i;
            break;
        }
    }
    unordered_map<int, int> m;
    for (int i = 0; i <= len; i++)
    {
        if ( ((currentBlock * squareroot) < arr[i]) && (arr[i] <= ((currentBlock + 1) * squareroot)))
        {
            m[arr[i]]++;
            if (m[arr[i]] > 1)
                return arr[i];
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 6,1,2, 3, 5, 4, 6 };
    int n = 6;

    cout << "Repeated number(s) in the array is:"<< getRepeatedNumber(arr, n) << endl;
}
Repeated number(s) in the array is:6

വായിക്കാൻ മാത്രമുള്ള അറേയിലെ ആവർത്തിച്ചുള്ള ഒന്നിലധികം ഘടകങ്ങളിൽ ഒന്ന് കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.*;
class arrayRepeatedElements
{
    public static int getRepeatedNumber(int[] arr, int len)
    {
        int squareroot = (int) Math.sqrt(len);
        int range = (len / squareroot) + 1;
        int freqCount[] = new int[range];
        for (int i = 0; i <= len; i++)
        {
            freqCount[(arr[i] - 1) / squareroot]++;
        }
        int currentBlock = range - 1;
        for (int i = 0; i < range - 1; i++)
        {
            if (freqCount[i] > squareroot)
            {
                currentBlock = i;
                break;
            }
        }
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i <= len; i++)
        {
            if ( ((currentBlock * squareroot ) < arr[i]) && ( arr[i] <= ((currentBlock + 1) * squareroot)))
            {
                freq.put(arr[i], 1);
                if (freq.get(arr[i])== 1)
                    return arr[i];
            }
        }
        return -1;
    }
    public static void main(String args[])
    {
        int[] arr = { 6,1, 2, 3, 5, 4, 6 };
        int n = 6;
        System.out.println("Repeated number(s) in the array is:"+getRepeatedNumber(arr, n));
    }
}
Repeated number(s) in the array is:6

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) എവിടെ "N" (അറേയുടെ ദൈർഘ്യം - 1) അതായത്, n - 1. കാരണം നമുക്ക് എല്ലാ ഘടകങ്ങളും സഞ്ചരിക്കേണ്ടതുണ്ട്.

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

sqrt (N) എവിടെ "N" (അറേയുടെ നീളം - 1) അതായത് n-1. അൽഗോരിത്തിന്റെ സ്വഭാവം കാരണം. ആദ്യം, ചതുരശ്ര (N) വലുപ്പത്തിന് തുല്യമായ വിഭാഗങ്ങൾക്കായി ഞങ്ങൾ കണക്കുകൂട്ടൽ നടത്തി.