படிக்க மட்டும் வரிசையில் பல மீண்டும் மீண்டும் கூறுகளில் ஏதேனும் ஒன்றைக் கண்டறியவும்  


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது மூலதன ஒன்று பேஸ்புக் கூகிள் உண்மையில் மைக்ரோசாப்ட் இடுகைகள்
அணி ஹாஷ்

சிக்கல் “படிக்க மட்டுமே வரிசையில் பல தொடர்ச்சியான கூறுகளில் ஒன்றைக் கண்டுபிடி” என்பது உங்களுக்கு படிக்க மட்டுமே வழங்கப்படுகிறது என்று கூறுகிறது வரிசை அளவு (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. தொகுப்பு “CurrentBlock” வரம்பு -1 க்கு.
  6. நான் <வரம்பு -1.
    1. FreqCount [i]> squareroot என்றால், currentBlock = i செய்து உடைக்கவும்.
  7. ஒரு அறிவிக்கவும் வரைபடம்.
  8. சொந்தமான கூறுகளைச் சரிபார்க்க வரைபடத்தில் பயணிக்கவும் “CurrentBlock”.
    1. பின்னர் arr [i] ஐ வைத்து வரைபடத்தின் விசையின் மதிப்பின் மதிப்பை அதிகரிக்கவும்.
    2. ஒரு விசையின் மதிப்பு 1 ஐ விட அதிகமாக இருந்தால், திரும்பவும் [i].
  9. வேறு வருவாய் -1 (உறுப்பு எதுவும் கிடைக்கவில்லை).

விளக்கம்

ஒரு வரிசையில் மீண்டும் மீண்டும் இருக்கும் உறுப்பைக் கண்டுபிடிக்க ஒரு கேள்வியைக் கொடுத்துள்ளோம், இதில் அனைத்து முழு எண்களும் 1 முதல் n வரையிலும், ஒரு வரிசையின் அளவு n + 1 ஆகவும் இருக்கும். இது மீண்டும் மீண்டும் ஒரு உறுப்பு இருப்பதைக் காண்பிப்பதால், அது n + 1 அளவைக் கொண்டுள்ளது.

மேலும் காண்க
நாப்சாக் சிக்கல்

ஒரு எளிய தீர்வு ஒரு ஹாஷ்மேப்பை உருவாக்கி ஒவ்வொரு உறுப்புகளின் அதிர்வெண் எண்ணிக்கையையும் வைத்திருத்தல். ஆனால் இந்த தீர்வுக்கு O (N) நேரம் மற்றும் O (N) இடம் தேவை. இதை விட சிறப்பாக நாம் செய்ய முடியுமா?

சதுர வேர் சிதைவுக்கு ஒத்த அணுகுமுறையை நாம் பயன்படுத்தலாம். இந்த அணுகுமுறை எங்கள் இட சிக்கலை O (sqrt (N)) ஆகக் குறைக்கும். அளவு சதுர (N) + 1 வரிசையை உருவாக்குகிறோம். மேலும் ar (i-1) / sqrt (n) சூத்திரத்தின் படி மதிப்புகளுடன் தொடர்புடைய குறியீடுகளை அதிகரிக்கவும். இதைச் செய்தபின், சதுரடி (N) ஐ விட அதிக அதிர்வெண் கொண்ட ஒரு குறியீட்டைக் கண்டுபிடிப்போம். இப்போது நாம் முந்தைய முறையைப் பயன்படுத்துவோம், ஆனால் இந்த வரம்பைச் சேர்ந்த உறுப்புகளுக்கு மட்டுமே.

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

வரிசை [] = {6, 1, 2, 3, 5, 4, 6}, n = 6

அளவு இருந்தால் n + 1 நாம் கடந்து செல்வோம் n அதற்கு. இப்போது நாம் அதன் சதுர மூலத்தைக் கண்டுபிடிக்க வேண்டும் n அதை சில மாறி சொல்லுக்கு சேமிக்கவும் சதுர ரூட்= 2. இப்போது நாம் வரிசையின் வரம்பைக் கண்டுபிடிக்க வேண்டும். நாங்கள் ஒரு வரிசை சொல்லை உருவாக்கப் போகிறோம் ஃப்ரீகவுண்ட் 'வரம்பு = 4' அளவு, (n / squareroot) + 1 ஆல் வரம்பைக் காண்போம்.

ஒவ்வொரு தனிமத்தின் அதிர்வெண்களையும் நாம் பயணிப்பதன் மூலம் உருவாக்கிய வரிசை வரம்பிற்குள் எண்ணுவோம். நாம் பயணிக்கும் ஒவ்வொரு முறையும் ஃப்ரீகவுன்ட் [(arr (i) -1) / squareroot] ++ ஐப் பின்பற்றுவோம்.

எங்கள் freqCount வரிசையில் பின்வரும் மதிப்புகளைக் கொண்டிருப்போம்.

மேலும் காண்க
ஒரு + b + c = d போன்ற வரிசையில் மிகப்பெரிய d ஐக் கண்டறியவும்

ஃப்ரீகவுண்ட்: [2,2,3,0]

அமைத்தல் தற்போதைய தொகுதி வரம்பு -1 அதாவது 3. நாம் பயணிப்போம் ஃப்ரீகவுண்ட் வரிசை. விட அதிகமான மதிப்பைக் கண்டால் சதுர ரூட் வரிசையில். FreqCount இன் 2 வது குறியீட்டில் இருப்பதைக் கண்டுபிடித்து, currentBlock ஐ i ஆக அமைத்து உடைக்கிறோம். நாங்கள் ஒரு அறிவிப்போம் ஹாஷ்மேப் மற்றும் உள்ளீட்டு வரிசையின் ஒவ்வொரு உறுப்புகளையும் கடந்து, எந்தவொரு உறுப்பு நடப்பு பிளாக் மற்றும் சதுரூட்டிற்கு சொந்தமானதா என்று பாருங்கள், ஆம் எனில், அதை ஒரு வரைபடத்தில் வைத்து, அந்த மதிப்பை [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) அதாவது n-1. வழிமுறையின் தன்மை காரணமாக. முதலில், சதுரடி (N) அளவிற்கு சமமான பிரிவுகளுக்கு கணக்கீடு செய்தோம்.