يحتوي على نسخة مكررة


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل
مجموعة تجزئة

لقد حصلنا على مجموعة وقد يحتوي على عناصر مكررة أو ربما لا. لذلك نحن بحاجة إلى التحقق مما إذا كان يحتوي على نسخة مكررة.

أمثلة

يحتوي على نسخة مكررة

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

الرسالة

يمكننا التحقق من المصفوفة بعدة طرق للتحقق مما إذا كانت تحتوي على نسخ مكررة أم لا. الطريقة الأكثر شيوعًا هي "طريقة القوة الغاشمة". لكن لها تعقيد زمني لـ O (n2) وهو جيد للأغراض الأكاديمية فقط. لكننا نحن الآخرون لحل مشكلتنا في تعقيد زمني أقل "طريقة مجموعة التجزئة" أو "طريقة جدول التجزئة" هذه الطريقة أكثر كفاءة من "طريقة القوة الغاشمة". تأخذ طريقة Hash Set التعقيد الزمني لـ O (n).

طريقة تعيين التجزئة

هذه الطريقة أبسط وأكثر كفاءة من غيرها. كل ما نحتاج إلى معرفته أن المجموعة لا تحتوي على نسخ مكررة. هذا يعني أنه إذا حاولنا إضافة قيمة مكررة يتم تعيينها ، فسوف يعطي خطأ. إذا استخدمنا هذه الطريقة ، فكل ما يتعين علينا القيام به هو مجرد حلقة فوق عناصر المصفوفة ، وإدراجها في مجموعة التجزئة. ثم قارن حجم المجموعة بالمصفوفة. إذا كانت لا تساوي التعيين ، فإن المصفوفة تحتوي على تكرارات أخرى لا.

خوارزمية

  1. أولاً ، نقوم بإنشاء دالة تأخذ مصفوفة كوسيطة.
  2. بعد ذلك ، في وظيفتنا ، نقوم بإنشاء مجموعة تحتوي على جميع قيم المصفوفة.
  3. لا تسمح المجموعة بالتكرارات ، وهذا يعني أنه إذا كانت المصفوفة تحتوي على تكرارات ، فسيكون حجمها مختلفًا عن حجم المجموعة.
  4. أخيرًا ، نقارن حجم كل من المصفوفة والمجموعة. إذا كان هناك اختلاف في حجمها ، فإن المصفوفة تحتوي على تكرارات وإلا ستكون جميع العناصر مميزة.

تفسير

في برنامجنا ، نستخدم مجموعة التجزئة للتحقق من التكرارات أولاً ، سنقوم بعمل وظيفة للتحقق. حيث سنقوم بعمل مجموعة تجزئة ونعطيها جميع قيم المصفوفة. بعد هذه المجموعة تزيل التكرارات إذا كانت تحتوي على أي منها وسيكون حجمها مختلفًا مقارنة بالمصفوفة وإلا فلن تؤثر على حجم المجموعة.

كود 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) حيث أن المساحة المستخدمة بواسطة جدول التجزئة تكون خطية مع عدد العناصر الموجودة فيه.