केवळ वाचनीय अ‍ॅरेमध्ये एकाधिक पुनरावृत्ती घटकांपैकी एक शोधा


अडचण पातळी हार्ड
वारंवार विचारले कॅपिटल वन फेसबुक Google खरंच मायक्रोसॉफ्ट करा
अरे हॅश

“केवळ वाचनीय अ‍ॅरेमध्ये एकाधिक पुनरावृत्ती घटकांपैकी एक शोधा” ही समस्या सांगते की समजा आपल्याला केवळ वाचन दिले गेले आहे अॅरे आकाराचे (एन + 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. सेट करा "वर्गमुळ" to sqrt (n).
  2. (एन / स्क्वेअररुट) + 1 वर श्रेणी सेट करा.
  3. आकार श्रेणीचा अ‍ॅरे तयार करा.
  4. यासह प्रत्येक घटकाची वारंवारता मोजा आणि ती संचयित करा (फ्रीकउंट ([एआर [i] - 1) / स्क्वेअररुट] ++).
  5. सेट करा “करंटब्लॉक” श्रेणी -1 पर्यंत.
  6. मी <श्रेणी -1 असताना.
    1. जर फ्रीकउंट [i]> स्क्वेअररुट असेल तर करंटब्लॉक = आय करा आणि ब्रेक करा.
  7. घोषित ए नकाशा.
  8. संबंधित घटकांची तपासणी करण्यासाठी नकाशामध्ये जा “करंटब्लॉक”.
    1. नंतर अरर [i] लावा आणि नकाशाच्या कीच्या मूल्याचे मूल्य वाढवा.
    2. किल्लीचे मूल्य 1 पेक्षा जास्त आढळल्यास अरर [i] परत करा.
  9. अन्य रिटर्न -1 (कोणताही घटक आढळला नाही).

स्पष्टीकरण

अ‍ॅरेमध्ये पुन्हा उपस्थित घटक शोधण्यासाठी आम्ही एक प्रश्न विचारला आहे ज्यामध्ये सर्व पूर्णांक 1 ते n पर्यंत आहेत आणि अ‍ॅरेचा आकार n + 1 आहे. हे एका पुनरावृत्ती घटकाची उपस्थिती दर्शविते म्हणूनच त्याचा आकार n + 1 आहे.

हॅशमॅप तयार करणे आणि प्रत्येक घटकांची वारंवारता संख्या ठेवणे हा एक सोपा उपाय आहे. परंतु या निराकरणासाठी ओ (एन) वेळ आणि ओ (एन) जागा आवश्यक आहे. आम्ही यापेक्षा चांगले करू शकतो?

स्क्वेअर रूट अपघटन सारखा असा दृष्टीकोन वापरु शकतो. हा दृष्टिकोन ओ (वर्ग) (एन) पर्यंतची आपली अवघडपणा कमी करेल. आम्ही चौरस (एन) आकाराचा अ‍ॅरे तयार करतो. १ आणि सूत्र एर (आय -१) / स्क्वेअर (एन) नुसार मूल्यांशी संबंधित निर्देशांक वाढवून ठेवतो. असे केल्यावर आम्हाला एक अनुक्रमणिका नक्कीच सापडेल ज्याची वारंवारता एसकेआरटी (एन) पेक्षा जास्त असेल. आता आम्ही मागील पद्धत वापरु पण फक्त या श्रेणीशी संबंधित घटकांसाठी.

हॅशिंग आणि काही मूलभूत गणिते समस्येच्या निराकरणात वापरली जातात. पुनरावृत्ती झालेला घटक शोधण्यासाठी आपण अ‍ॅरे आणि आकारापेक्षा कमी 1 व्हॅल्यू पास करू. याचे निराकरण करण्यासाठी एक उदाहरण घेऊ:

अ‍ॅरे [] = {6, 1, 2, 3, 5, 4, 6}, एन = 6

आकार असेल तर एन + 1 मग आम्ही पार करू n ते. याचा वर्गमूल शोधून काढावा लागेल n आणि त्यास काही व्हेरिएबल म्हणा वर्गमुळ= 2. आता आपल्याला अ‍ॅरेची श्रेणी शोधावी लागेल. आपण एक अ‍ॅरे बनवणार आहोत freqCount आकार 'श्रेणी = 4', आम्हाला (एन / स्क्वेअररुट) + 1 द्वारे श्रेणी सापडेल.

आम्ही ट्रॅव्हर्सिंगद्वारे तयार केलेल्या अ‍ॅरेच्या श्रेणीतील प्रत्येक घटकाची वारंवारता मोजू. प्रत्येक वेळी आम्ही ट्रॅव्हस केल्यावर आम्ही फ्रीकउंट [(अरर (आय) -1) / स्क्वेअररुट] ++ चे अनुसरण करू.

आपल्या फ्रीक्काउंट अ‍ॅरेमध्ये खालील व्हॅल्यूज असतील.

फ्रीकउंट: [२,२,2,2,3,0,०]

उभे करणे उभारणे चालू ब्लॉक 1 च्या श्रेणीपर्यंत - आम्ही ते मागे जाऊ freqCount रचना. आम्हाला त्यापेक्षा अधिक मूल्य आढळल्यास वर्गमुळ अ‍ॅरे मध्ये. आम्हाला आढळते की फ्रिककउंटच्या दुसर्‍या निर्देशांकात आणि करंटब्लॉक मी आणि ब्रेक सेट केला आहे. आम्ही घोषित करू हॅशमॅप आणि इनपुट अ‍ॅरेच्या प्रत्येक घटकाचा आढावा घ्या आणि घटकांपैकी कोणताही सध्याचा ब्लॉक आणि स्क्वेअररुटचा आहे की नाही हे तपासा, असल्यास होय, आम्ही ते एका नकाशामध्ये ठेवले आणि ते मूल्य परत केले [i].

आपले आउटपुट होईल: 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन) जेथे “एन” (अ‍ॅरेची लांबी - 1) म्हणजेच एन - १ आहे कारण आपल्याला सर्व घटकांना मागे टाकावे लागेल.

स्पेस कॉम्प्लेक्सिटी

चौरस (एन) जेथे “एन” (अ‍ॅरेची लांबी - 1) म्हणजे एन -1 आहे. अल्गोरिदमच्या स्वभावामुळे. प्रथम, आम्ही वर्गफलक (एन) च्या आकाराच्या समान विभागांसाठी गणना केली.