கூறுகள் ஒரு வரம்பிற்கு மட்டுப்படுத்தப்படாதபோது கொடுக்கப்பட்ட வரிசையில் நகல்களைக் கண்டறியவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் உண்மை MAQ யுஎச்ஜி ஆப்டம்
அணி ஹேஷிங்

சிக்கல் “உறுப்புகள் வரம்பிற்குள் வரையறுக்கப்படாதபோது கொடுக்கப்பட்ட வரிசையில் நகல்களைக் கண்டுபிடி” என்பது உங்களிடம் உள்ளது என்று கூறுகிறது வரிசை n ஐ உள்ளடக்கியது முழு. வரிசையில் இருந்தால் நகல் கூறுகளைக் கண்டுபிடிக்க சிக்கல் அறிக்கை. அத்தகைய உறுப்பு எதுவும் இல்லை என்றால் திரும்ப -1.

உதாரணமாக

கூறுகள் ஒரு வரம்பிற்கு மட்டுப்படுத்தப்படாதபோது கொடுக்கப்பட்ட வரிசையில் நகல்களைக் கண்டறியவும்

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

விளக்கம்

இந்த வரிசையில் 2 மற்றும் 7 மட்டுமே நகல் கூறுகள்.

[134, 567, 134, 456, 1000, 567, 7]
134, 567

விளக்கம்

இந்த வரிசையில் 134 மற்றும் 567 மட்டுமே நகல் கூறுகள்.

ஒரு வரிசையில் நகல் கூறுகளைக் கண்டறிய வழிமுறை

  1. அறிவிக்க வரைபடம்.
  2. வரிசையின் உறுப்பு மற்றும் அதன் அதிர்வெண் வரைபடத்தில் சேமிக்கவும்.
  3. அறிவிக்கவும் பூலியன் மாறி நகல் நகல் உறுப்பு இருக்கிறதா இல்லையா என்பதைச் சரிபார்க்க.
  4. வரைபடத்தின் மீது சொடுக்கவும், எந்த உறுப்புக்கு 1 ஐ விட அதிர்வெண் உள்ளது என்பதை சரிபார்க்கவும்.
  5. அதிர்வெண் 1 ஐ விட அதிகமாக இருந்தால், உறுப்பை அச்சிட்டு, நகலை உண்மைக்கு துவக்கவும்.
  6. நிபந்தனை திருப்தி அடைந்தால் நகல் தவறானதா என சரிபார்க்கவும், பின்னர் -1 ஐ அச்சிடவும்.

விளக்கம்

நாங்கள் ஒரு சிக்கலைக் கொடுத்துள்ளோம், அதில் ஒரு வரிசையில் உள்ள நகல் கூறுகளைத் தீர்மானித்து அந்த கூறுகளை அச்சிட வேண்டும். இதற்காக, நாம் ஒரு பயன்படுத்தப் போகிறோம் ஹாஷ்மேப் ஒவ்வொரு வரிசை உறுப்புகளின் அதிர்வெண்களை சேமிக்க. 1 ஐ விட அதிகமாக இருக்கும் அதிர்வெண்கள், வரிசையில் தன்னை மீண்டும் மீண்டும் எண்ணுகின்றன. அதாவது அந்த எண்ணின் நகல்.

ஒரு வரிசை மற்றும் அதன் நீளம் என இரண்டு வாதங்களை நாங்கள் கடந்துவிட்டோம். இப்போது பூலியன் மாறி தவறானதாக துவக்கப்படும் இன்னும் ஒரு மாறியை அறிவிக்கவும். பின்னர் அதை சரிபார்க்கவும், பின்னர் எந்த நகல் உறுப்புகளையும் நாம் காணவில்லை என்றால் நகல் பொய்யாக இருக்கிறது, அது உண்மையாக இருக்கும். இந்த வரைபடத்தைப் பயன்படுத்தி, அதிர்வெண் 1 ஐ விட அதிகமாக உள்ள உறுப்பைக் கண்டுபிடி, அந்த உறுப்புகளை அச்சிடுவோம். ஒரு வரிசையில் நகல் கூறுகளை நாம் எப்படிக் கண்டுபிடிப்போம்.

ஒரு உதாரணத்தைக் கருத்தில் கொள்வோம்:

arr [] = {2,4,6,3,1,2,4,7};

i = 0, arr [i] = 2; freq = {2: 1}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

i = 5, arr [i] = 2; freq = {2: 2,4: 1,6: 1,3: 1,1: 1} // '2' அதிர்வெண்ணை 1 முதல் 2 வரை அதிகரிக்கும்,

i = 6, arr [i] = 4; freq = {2: 2,4: 2,6: 1,3: 1,1: 1} // '4' அதிர்வெண்ணை 1 முதல் 2 வரை அதிகரிக்கும்,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

எங்களிடம் வரைபடத்தில் ஃப்ரீக் உள்ளது: {2: 2,4: 2,6: 1,3: 1,1: 1,7: 1}

இப்போது வரைபடத்தின் மீது மீண்டும் சொல்லுங்கள், எந்த மதிப்பு 1 ஐ விட அதிகமாக உள்ளது என்பதைக் கண்டுபிடி. பூலியன் மாறி நகலை தவறானது என்று நாங்கள் ஏற்கனவே துவக்கியுள்ளோம், எனவே எந்த அதிர்வெண் 1 ஐ விட அதிகமாக உள்ளது என்பதை சரிபார்க்கும்போது, ​​நகல் உண்மை என புதுப்பிக்கப் போகிறோம். பொய்யானது என நகல் கொண்ட வட்டத்திலிருந்து நாம் வெளியே வந்தால், இதன் பொருள் நகல் உறுப்பு ஒரு வரிசையில் இல்லை.

2 மற்றும் 4 ஆகியவை நகல் கூறுகள் என்பதை விட அதிக அதிர்வெண் கொண்டவை என்பது தெளிவாகிறது.

எங்கள் வெளியீடு [2 4] ஆகிறது. எனவே ஒரு வரிசையில் நகல் கூறுகளை எவ்வாறு கண்டுபிடிப்பது என்பதற்கு இது ஒரு எடுத்துக்காட்டு.

குறியீடு

ஒரு வரிசையில் நகல் கூறுகளைக் கண்டுபிடிக்க சி ++ குறியீடு

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}
4 2

ஒரு வரிசையில் நகல் கூறுகளைக் கண்டுபிடிக்க ஜாவா குறியீடு

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}
2 4

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. இதனால் “கூறுகள் ஒரு வரம்பிற்கு மட்டுப்படுத்தப்படாதபோது கொடுக்கப்பட்ட வரிசையில் நகல்களைக் கண்டுபிடி” சிக்கல் நேரியல் நேர சிக்கலைக் கொண்டுள்ளது.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. விண்வெளி சிக்கலானது நேரியல் ஆகும், ஏனெனில் மோசமான நிலையில் நாம் எல்லா தனித்துவமான கூறுகளையும் கொண்டிருக்கலாம்.