Элементүүд хүрээ хязгаарлагдаагүй тохиолдолд өгөгдсөн массиваас хуулбарыг ол


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Factset MAQ UHG Optum
Array Хаширч байна

“Элементүүд хүрээ хязгаарлагдаагүй байхад өгөгдсөн массиваас хуулбарыг олох” гэсэн асуудал танд байна массив 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. Тунхагла Boolean хувьсагч хуулбар давхардсан элемент байгаа эсэхийг шалгах.
  4. Газрын зураг дээр давтаж, аль элементийн давтамж 1-ээс их байгааг шалгана уу.
  5. Хэрэв давтамж нь 1-ээс их бол элементийг хэвлээд, хуулбарыг үнэн болгоно.
  6. Нөхцөл хангаж байвал давхар хуулбар худлаа эсэхийг шалгаад -1 гэж хэвлэ.

Тайлбар

Бид массив дахь давхардсан элементүүдийг тодорхойлж, эдгээр элементүүдийг хэвлэх ёстой гэсэн асуудлыг өгсөн. Үүний тулд бид a HashMap массивын элемент бүрийн давтамжийг хадгалах зориулалттай. 1-ээс их давтамжууд нь массив дахь тоо давтагдана гэсэн үг юм. Энэ нь тухайн дугаарын давхардал гэсэн үг юм.

Бид хоёр аргументийг массив болон түүний уртаар дамжуулсан болно. Boolean хувьсагч болох өөр нэг хувьсагчийг худал гэж зарла. Дараа нь хэрэв бид ямар ч давхардсан элемент олохгүй бол дараа нь шалгана уу хуулбар хуурамч хэвээр байгаа бол энэ нь үнэн байх болно. Дараа нь энэ газрын зургийг ашиглан 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}

бидэнд газрын зураг дээр freq байна: {2: 2,4: 2,6: 1,3: 1,1: 1,7: 1}

Одоо газрын зураг дээр давтаж, аль утга давтамж 1-ээс их болохыг олж мэд. Бид энд Boolean хувьсагчийн хуулбарыг хуурамч гэж эхлүүлсэн тул аль давтамж нь 1-ээс их болохыг шалгахдаа давхардсан хувилбарыг үнэн болгож шинэчлэх болно. Хэрэв бид давталтаас хуурамч гэсэн давталттай гарч ирвэл энэ нь массив дотор давхардсан элемент байхгүй гэсэн үг юм.

2 ба 4-ийн давтамж нь давхардсан элементүүд гэсэн үгээс их байх нь ойлгомжтой.

Манай бүтээгдэхүүн [2 4] болж хувирдаг. Тиймээс энэ нь массиваас давхардсан элементүүдийг хэрхэн олж болохыг харуулсан жишээ байв.

код

Массив дахь давхардсан элементүүдийг олох C ++ код

#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

Массив дахь давхардсан элементүүдийг олох Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Тиймээс "Элементүүд хязгаараар хязгаарлагдахгүй тохиолдолд өгөгдсөн массиваас давхардсан тоог олох" асуудал нь цаг хугацааны шугаман нарийн төвөгтэй байдаг.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Сансрын нарийн төвөгтэй байдал нь мөн шугаман шинжтэй байдаг, учир нь хамгийн муу тохиолдолд бид бүх ялгаатай элементүүдтэй байж болно.