केवल पढ़ने के लिए कई सरणी तत्वों में से किसी एक को खोजें


कठिनाई स्तर कठिन
में अक्सर पूछा एक राजधानी Facebook गूगल वास्तव में माइक्रोसॉफ्ट Pinterest
ऐरे हैश

समस्या "केवल पढ़ने में कई दोहराए जाने वाले तत्वों में से किसी एक को ढूंढें" बताता है कि आपको केवल पढ़ने के लिए दिया गया है सरणी आकार का (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. सेट "वर्गमूल" to sqrt (n)।
  2. (N / squareroot) + 1 तक सीमा निर्धारित करें।
  3. आकार श्रेणी का एक सरणी बनाएं।
  4. इसके साथ प्रत्येक तत्व की आवृत्ति को गिनें और संग्रहीत करें (freqCount [(arr [i] - 1) / squareroot] ++)।
  5. सेट "करेंटब्लॉक" रेंज -1 तक।
  6. जबकि मैं <रेंज -1।
    1. अगर freqCount [i]> स्क्वेररूट, तो करंटब्लॉक = i और ब्रेक करें।
  7. डिक्लेयर ए नक्शा.
  8. उन तत्वों की जांच करने के लिए एक नक्शे में पार करें जो संबंधित हैं "करेंटब्लॉक".
    1. फिर गिरफ्तारी [i] डालें और नक्शे की कुंजी के मूल्य को बढ़ाएं।
    2. यदि एक कुंजी का मान 1 से अधिक पाया जाता है, तो गिरफ्तारी लौटें [i]।
  9. एल्स रिटर्न -1 (कोई तत्व नहीं मिला)।

व्याख्या

हमने एक सरणी में मौजूद बार-बार मौजूद तत्व का पता लगाने के लिए एक प्रश्न दिया है जिसमें सभी पूर्णांक 1 से n तक होते हैं और एक सरणी का आकार n + 1 है। चूंकि यह एक दोहराया तत्व की उपस्थिति को दर्शाता है, इसीलिए इसका आकार n + 1 है।

एक सरल समाधान है कि हमशैप बनाएं और प्रत्येक तत्वों की आवृत्ति गणना रखें। लेकिन इस समाधान के लिए O (N) समय और O (N) स्थान की आवश्यकता होती है। क्या हम इससे बेहतर कर सकते हैं?

हम एक दृष्टिकोण का उपयोग कर सकते हैं जो वर्गमूल अपघटन के समान है। इस दृष्टिकोण से O (sqrt (N)) के लिए हमारी अंतरिक्ष जटिलता कम हो जाएगी। हम आकार का एक वर्ग sqrt (N) + 1. बनाते हैं और सूत्र पकड़े गए सूत्र (i-1) / sqrt (n) के अनुसार मूल्यों के अनुरूप वेतन वृद्धि करते रहते हैं। ऐसा करने के बाद, हम निश्चित रूप से एक सूचकांक का पता लगाएंगे जिसमें sqrt (N) से अधिक आवृत्ति होती है। अब हम पिछली विधि का उपयोग करेंगे लेकिन केवल इस श्रेणी से संबंधित तत्वों के लिए।

hashing और समस्या के समाधान में कुछ बुनियादी गणित का उपयोग किया जाता है। दोहराए गए तत्व का पता लगाने के लिए हम एक सरणी और एक मान पास करेंगे जो सरणी के आकार से 1 कम है। इसे हल करने के लिए एक उदाहरण लेते हैं:

सरणी [] = {6, 1, 2, 3, 5, 4, 6}, n = 6

यदि आकार है + 1 n फिर हम पास होंगे n यह करने के लिए। अब हमें इसका वर्गमूल निकालना है n और इसे कुछ वैरिएबल स्टोर करने के लिए कहें वर्गमूल= २। अब हमें सरणी की सीमा का पता लगाना है। हम एक सरणी कहने जा रहे हैं फ्रीकाउंट आकार 'श्रेणी = 4' के अनुसार, हम इस श्रेणी को (n / squareroot) + 1 से देखेंगे।

हम प्रत्येक तत्व की आवृत्तियों की गणना करेंगे जो हमने ट्रैवर्सिंग द्वारा बनाई गई सरणी की सीमा के भीतर की है। हर बार जब हम आगे बढ़ते हैं तो हम freCount का अनुसरण करेंगे [(गिरफ्तारी (i) -1) / स्क्वेररूट] ++।

हम अपने freqCount सरणी में निम्नलिखित मान रखेंगे।

फ़्रीककाउंट: [२,२,३,०]

की स्थापना चालू सीमा -1 तक वह है 3. हम इसे पीछे छोड़ देंगे फ्रीकाउंट सरणी। यदि हम इससे अधिक मूल्य पाते हैं वर्गमूल सरणी में। हम पाते हैं कि freqCount के 2 सूचकांक में और i और ब्रेक के लिए currentBlock सेट करें। हम घोषणा करेंगे हैश मैप और इनपुट ऐरे के प्रत्येक तत्व को ट्रेस करें और देखें कि क्या कोई तत्व करंटब्लॉक और स्क्वॉयररूट से संबंधित है, यदि हाँ, तो हम इसे मैप में डालते हैं और गिरफ्तारी के मूल्य को वापस करते हैं [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) अर्थात, n - 1. क्योंकि हमें सभी तत्वों का पता लगाना है।

अंतरिक्ष जटिलता

sqrt (N) जहां "एन" है (लंबाई की लंबाई - 1) यानी, एन -1। एल्गोरिथ्म की प्रकृति के कारण। पहले, हमने sqrt (N) के आकार के बराबर वर्गों के लिए गणना की।