কেবলমাত্র পঠনযোগ্য অ্যারেতে একাধিক পুনরাবৃত্তি উপাদানগুলির মধ্যে একটি আবিষ্কার করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় ক্যাপিটাল ওয়ান ফেসবুক গুগল প্রকৃতপক্ষে মাইক্রোসফট পিন্টারেস্ট
বিন্যাস কাটা

সমস্যাটি "কেবলমাত্র পঠনযোগ্য অ্যারেতে একাধিক পুনরাবৃত্তিকারী উপাদানগুলির মধ্যে একটি আবিষ্কার করুন" বলে উল্লেখ করে যে ধরুন আপনাকে কেবল পঠনযোগ্য দেওয়া হয়েছে বিন্যাস আকারের (এন + 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. যদি ফ্রিককাউন্ট [i]> বর্গক্ষেত্র হয় তবে কারেন্টব্লক = i করুন এবং বিরতি দিন।
  7. ঘোষণা করুন ক মানচিত্র.
  8. যে উপাদানগুলির অন্তর্ভুক্ত তা পরীক্ষা করতে মানচিত্রে প্রবেশ করুন "কারেন্টব্লক".
    1. তারপরে আর্ট [i] রাখুন এবং মানচিত্রের কী এর মানটির মান বাড়ান।
    2. যদি একটি কী এর মান 1 এরও বেশি পাওয়া যায় তবে ফিরে আসুন [i]।
  9. অন্য রিটার্ন -1 (কোনও উপাদান পাওয়া যায় নি)।

ব্যাখ্যা

একটি অ্যারেতে উপস্থিত পুনরাবৃত্ত উপাদানটি খুঁজে বের করার জন্য আমরা একটি প্রশ্ন দিয়েছি যার মধ্যে সমস্ত পূর্ণসংখ্যা 1 থেকে n অবধি এবং অ্যারের আকার n + 1 হয়। যেহেতু এটি একটি পুনরাবৃত্ত উপাদানগুলির উপস্থিতি দেখায় তাই এটির n + 1 এর আকার রয়েছে।

একটি সহজ সমাধান হ্যাশম্যাপ তৈরি করা এবং প্রতিটি উপাদানের ফ্রিকোয়েন্সি গণনা রাখা। তবে এই সমাধানের জন্য ও (এন) সময় এবং ও (এন) স্থান প্রয়োজন। আমরা কি এর চেয়ে আরও ভাল করতে পারি?

বর্গমূলের পচে যাওয়ার অনুরূপ একটি পন্থা আমরা ব্যবহার করতে পারি। এই পদ্ধতির সাহায্যে আমাদের স্পেস জটিলতা হ্রাস পাবে ও (স্কয়ার্ট (এন))। আমরা স্কয়ার্ট (এন) + 1 আকারের একটি অ্যারে তৈরি করি এবং সূত্র অ্যারের (i-1) / স্ক্র্যাট (এন) অনুযায়ী মানগুলির সাথে সূচকগুলি বর্ধিত রাখি। এটি করার পরে, আমরা অবশ্যই একটি সূচক খুঁজে বের করব যা স্কয়ার্ট (এন) এর চেয়ে বেশি ফ্রিকোয়েন্সি রয়েছে। এখন আমরা পূর্ববর্তী পদ্ধতিটি ব্যবহার করব তবে কেবলমাত্র এই ব্যাপ্তির সাথে যুক্ত উপাদানগুলির জন্য।

হ্যাশ এবং কিছু প্রাথমিক গণিত সমস্যার সমাধানে ব্যবহৃত হয়। পুনরাবৃত্তি উপাদানটি খুঁজতে আমরা একটি অ্যারে এবং অ্যারের আকারের চেয়ে কম 1 মান পাস করব। এর সমাধানের জন্য একটি উদাহরণ নেওয়া যাক:

অ্যারে [] = {6, 1, 2, 3, 5, 4, 6 n, n = 6

যদি আকার হয় , n + 1 তাহলে আমরা পাস করব n এটা। এখন এর বর্গমূল বের করতে হবে n এবং এটি কিছু পরিবর্তনশীল বলে সংরক্ষণ করুন বর্গমূল= 2। এখন আমাদের অ্যারের পরিসরটি খুঁজে বের করতে হবে। আমরা একটি অ্যারে বলতে তৈরি করতে যাচ্ছি freqCount আকারের 'রেঞ্জ = 4', আমরা (এন / স্কয়াররুট) + 1 দ্বারা সীমাটি পেয়ে যাব।

আমরা traversing দ্বারা তৈরি অ্যারের পরিসীমা মধ্যে প্রতিটি উপাদান এর ফ্রিকোয়েন্সি গণনা করব। প্রতিবার যখন আমরা ট্র্যাভার করব আমরা ফ্রিকাউন্ট অনুসরণ করব [(আরআর (আই) -1) / স্ক্রোরুট] ++।

আমরা আমাদের ফ্রিককাউন্ট অ্যারেতে নিম্নলিখিত মানগুলি শেষ করব।

ফ্রিককাউন্ট: [২,২,৩,০]

ঠিককরা কারেন্টব্লক 1 -3 এর পরিসীমা XNUMX হ'ল আমরা এটিকে পার করব 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) অর্থাত্, n - 1. কারণ আমাদের সমস্ত উপাদানকে অতিক্রম করতে হবে।

স্পেস জটিলতা ity

স্কয়ার্ট (এন) কোথায় "এন" (অ্যারের দৈর্ঘ্য - 1) অর্থাৎ এন -1 কারণ অ্যালগরিদমের প্রকৃতি। প্রথমত, আমরা স্কয়ার্ট (এন) এর আকারের সমান বিভাগগুলির জন্য গণনা করেছি।