வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டறியவும்


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

பொருளடக்கம்

சிக்கல் அறிக்கை

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

உதாரணமாக

Array = {1 , 2 , 5 , 6 , 2 , 5}
3 4

வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டறியவும்

Array = {1 , 2 , 3 , 4}
n

வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டறியவும்

அணுகுமுறை (ஹாஷ்செட்டைப் பயன்படுத்துதல்)

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

அல்காரிதம்

  1. ஹாஷ் தொகுப்பைத் தொடங்கவும் குறி [முழு எண்] இருக்கும் கூறுகளை சேமிக்க.
  2. ஒவ்வொரு உறுப்புக்கும் i வரிசையில்:
    • கூட்டு i க்கு குறி
  3. பட்டியல் / திசையன் தொடங்கவும் விளைவாக வரிசையில் காணாமல் போன கூறுகளை சேமிக்க
  4. ஒவ்வொரு உறுப்புக்கும் வரம்பில்: [1, N]:
    • If இல் இல்லை குறி:
      • இதைச் சேர்க்கவும் விளைவாக
  5. திரும்ப விளைவாக
  6. முடிவை அச்சிடுங்கள்

வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டுபிடிப்பதை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

ஜாவா திட்டம்

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}
3 4

ஒரு வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டுபிடிப்பதற்கான சிக்கலான பகுப்பாய்வு

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

ஓ (என்) முழு வரிசையையும் ஒரு முறை முழு எண்ணாகக் குறிக்கும்போது. N = வரிசையின் அளவு.

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

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

அணுகுமுறை (இடத்தில் மாற்றம்)

இந்த சிக்கலில் கவனிக்க வேண்டிய ஒரு விஷயம்: “வரிசை எப்போதும் அதன் அளவை விட குறைவாகவோ அல்லது சமமாகவோ இருக்கும். இதன் பொருள் பல தனித்துவமான கூறுகள் உள்ளன. மேலும், காணாமல் போன கூறுகள் எப்போதும் N ஐ விட குறைவாக இருக்கும் (வரிசையின் அளவு). இந்த தடையைப் பயன்படுத்தி, ஒரு முழு எண்ணின் இருப்பை ஒருவிதத்தில் சேமிக்க வரிசையைப் பயன்படுத்தலாம். உதாரணமாக, நாம் எழுதலாம் என்று வைத்துக் கொள்ளுங்கள் சரி தவறு ஒரு உறுப்பு குறியீட்டில் முறையே அதன் இருப்பு / இல்லாததைக் குறிக்க. எங்கள் விஷயத்தில், வரிசையில் ஏற்கனவே கூறுகள் உள்ளன, எனவே இந்த வகையான சேமிப்பு / நினைவூட்டல் சாத்தியமில்லை. இருப்பினும், எல்லா கூறுகளும் நேர்மறையானவை என்பதை நாங்கள் அறிந்திருப்பதால், வரிசையில் ஒரு உறுப்பைக் கண்டிருக்கிறோமா இல்லையா என்பதைக் குறிக்கும் அடையாளமாக “எதிர்மறை” ஐப் பயன்படுத்தலாம். சில குறியீட்டில் சேமிக்கப்பட்ட உண்மையான மதிப்பைப் பயன்படுத்துவதன் மூலம் நாம் பெற முடியும் என்பதை நினைவில் கொள்க அறுதி() ஒரு முழு எண்ணின் முழுமையான மதிப்பை வழங்கும் செயல்பாடு. இந்த வழியில், வரிசை ஒரு ஹாஷ் வரைபடம் மற்றும் ஒரு கொள்கலன் என இரண்டையும் பயன்படுத்தலாம்.

எடுத்துக்காட்டாக, வரிசையில் '2' என்ற ஒரு உறுப்பை நாம் பார்த்திருந்தால், வரிசை [1] = -1 * வரிசை [1] ஐ ஒதுக்கலாம், இது உறுப்பு 2 வரிசையில் காணப்படுகிறது என்பதை நமக்குத் தெரிவிக்கும்.

இந்த தந்திரம் நாம் குறியீட்டில் ஒரு உறுப்பைக் கண்டிருந்தால் சேமிப்பதற்கான இடத்தில் வரிசையை கையாளும் i. முடிந்ததும், எதிர்மறை அல்லாத அனைத்து முழு எண்களையும் கண்டுபிடிக்க [1, N] வரம்பில் ஒரு சுழற்சியை இயக்கலாம் (அதாவது அவை காணப்படவில்லை என்று பொருள்) எனவே, தேவையான முடிவை அச்சிடுக. நாம் இருந்தால் மட்டுமே இது சாத்தியமாகும் என்பதை நினைவில் கொள்க அனுமதி வரிசையை மாற்ற.

அல்காரிதம்

  1. ஒவ்வொரு உறுப்புக்கும் வரிசையில்:
    • வரிசை என்றால் [i - 1]> 0:
      • இதை எதிர்மறையாக அமைக்கவும், அல்லது, வரிசை [i - 1] * = -1;
  2. பட்டியல் / திசையன் தொடங்கவும் விளைவாக விடுபட்ட அனைத்து கூறுகளையும் சேமிக்க
  3. ஒவ்வொரு முழு எண் [1, N] வரம்பில் (வரிசையின் N = அளவு):
    • If வரிசை [i]> 0
      • இந்த உறுப்பைச் சேர்க்கவும் i க்கு விளைவாக
  4. திரும்ப விளைவாக
  5. முடிவை அச்சிடுங்கள்

வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டுபிடிப்பதை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

ஜாவா திட்டம்

import java.util.*;
import java.lang.Math;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

ஒரு வரிசை லீட்கோட் தீர்வில் காணாமல் போன அனைத்து எண்களையும் கண்டுபிடிப்பதற்கான சிக்கலான பகுப்பாய்வு

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

ஓ (என்) விடுபட்ட கூறுகளைக் கண்டறிய உள்ளீட்டைப் பொருட்படுத்தாமல் வரிசையின் இரண்டு பாஸ்களை இயக்குகிறோம். N = வரிசையின் அளவு.

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

ஓ (1) நிலையான நினைவக இடத்தைப் பயன்படுத்துவதால்.