نقل لري


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه
پیشه ځورول

موږ ته ورکړل شو سور او دا ممکن د عکس عناصر ولري یا شاید نه وي. نو موږ اړتیا لرو ګورو چې دا پکې نقل شتون لري که نه.

مثالونه

نقل لري

[1, 3, 5, 1]
true
[“apple”, “mango”, “orange”, “mango”]
true
[22.0, 4.5, 3.98, 45.6, 13.54]
false

او کړنلاره

موږ کولی شو په څو لارو کې یو سیر وګورو چې دا چیک کړئ چې ایا دا عکسونه لري یا نه. ترټولو عامه میتود د "وحشي ځواک میتود" دی. مګر دا د O (n) وخت پیچلتیا لري2) او دا یوازې د علمي اهدافو لپاره ښه دی. مګر موږ بل د خپلې ستونزې د کم وخت پیچلتیا کې حل کولو لپاره "د هش سیټ میتود" یا "د هش میز میز" دا میتود د "بروټ فورس میتود" څخه خورا ډیر اغیزمن دی. د هش سیټ میتود د O (n) وخت پیچلتیا اخلي.

د هش سیټ میتود

دا میتود د نورو په پرتله حتی ساده او موثر دی. ټول موږ پوهیدو ته اړتیا لرو چې سیټ نقلونه نلري. د دې معنی دا ده چې که موږ هڅه وکړو چې دوه چنده ارزښت وټاکل شو دا به تیروتنه وکړي. که موږ دا میتود وکاروو ټول هغه څه چې موږ یې باید وکړو یوازې د سرې عنصرو څخه پای ته رسي ، هغه په ​​هش سیټ کې دننه کړئ. بیا د سیټ اندازه صف ته پرتله کړئ. که دا د سیټ سره مساوي نه وي نو په سر کې ورته نقلونه شتون لري نه.

الګوریتم

  1. لومړی ، موږ یو فنکشن رامینځته کوو چې د دلیل په توګه سرای اخلي.
  2. له هغې وروسته ، زموږ په فنکشن کې ، موږ یو سیټ رامینځته کوو چې د صفونو ټول ارزښت پکې لري.
  3. سیټ نقلونو ته اجازه نه ورکوي ، پدې معنی چې که په سر کې نقلونه شامل وي نو د هغې اندازه به د سیټ اندازې څخه توپیر ولري.
  4. په نهایت کې ، موږ د دواړه سرې او سیټ اندازه پرتله کوو. که چیرې د دوی اندازې کې توپیر شتون ولري نو بیا سرنی نقلونه لري نور ټول عناصر توپیر لري.

تشریح

زموږ په برنامه کې موږ د هیټ سیټ کارولو لپاره د عکسونو چک کولو لپاره لومړی ، موږ به د چک کولو لپاره یو فعالیت جوړ کړو. په کوم کې چې موږ به یو hash سیټ جوړ کړو او دا به د صفونو ټول ارزښتونه ورکړو. وروسته لدې سیټ نقلونه لرې کوي که چیرې دا یو ولري او د هغې اندازه به د سرنی په پرتله توپیر ولري نه نو دا به د سیټ اندازه اغیزه ونلري.

C ++ کوډ چیک کولو لپاره چې که په آرਾਰੇ کې کاپي شتون لري

#include <iostream>
#include <unordered_set>
using namespace std;

bool contain_duplicate(int arr[], int n)
{
    unordered_set<int> myset;
    bool flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (myset.find(arr[i]) == myset.end())
            myset.insert(arr[i]);

        else
        {
            flag = 1;
            break;
        }

    }
    return flag;
}
int main()
{
    int arr[] = {1, 5, 2, 4, 3, 7, 8, 9, 1};
    int n = sizeof(arr) / sizeof(int);

    cout<< boolalpha <<contain_duplicate(arr, n);
    return 0;
}
true

د جاوا کوډ چیک کولو لپاره چې که په صف کې کاپي شتون لري

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class contain_duplicate
{

    public static boolean solution(Integer [] array)
    {

        Set<Integer> myset = new HashSet<> (Arrays.asList(array));

        if(array.length!=myset.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Integer [] array = { 1, 2, 3, 6, 4, 9, 8, 1};
        System.out.println(solution(array));

    }
}
true

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n) چیرې چې "n" د صفونو اندازه ده.

د ځای پیچلتیا

O (n) لکه څنګه چې د هش مېز لخوا کارول شوی ځای په هغه کې د عناصرو شمیر سره خط دی.