إزالة المكررات بكفاءة من مصفوفات جافا

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

جدول المحتويات

• استخدام مصفوفة مؤقتة
• استخدام مؤشر منفصل
• استخدام طريقة Arrays.sort()
• مقارنة الطرق

استخدام مصفوفة مؤقتة

تتكرر هذه الطريقة البسيطة عبر المصفوفة المدخلة. يتم التحقق من كل عنصر مقابل مصفوفة مؤقتة تحتوي فقط على العناصر الفريدة التي تم مواجهتها حتى الآن. إذا لم يتم العثور على عنصر في المصفوفة المؤقتة، فسيتم إضافته. على الرغم من سهولة فهمها، إلا أن بنية الحلقة المتداخلة تؤدي إلى تعقيد زمني قدره O(n²)، مما يجعلها غير فعالة للمصفوفات الكبيرة.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesTempArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0]; 
        }

        int[] uniqueArr = new int[arr.length]; 
        int uniqueCount = 0;

        for (int i = 0; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < uniqueCount; j++) {
                if (arr[i] == uniqueArr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount); 
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 4, 4, 5, 5, 5};
        int[] uniqueArr = removeDuplicatesTempArray(arr);
        System.out.println("المصفوفة الأصلية: " + Arrays.toString(arr));
        System.out.println("المصفوفة بعد إزالة المكررات: " + Arrays.toString(uniqueArr));
    }
}

التعقيد الزمني: O(n²)
التعقيد المكاني: O(n)

استخدام مؤشر منفصل

تحسن هذه الطريقة كفاءة المساحة عن طريق تعديل المصفوفة الأصلية في مكانها. تستخدم مؤشرًا منفصلًا لتتبع موضع العنصر الفريد التالي. يتم تكرار المصفوفة، ويتم نقل العناصر الفريدة إلى المواضع التي يشير إليها هذا المؤشر. على الرغم من كفاءتها في استخدام المساحة (O(1))، إلا أنها لا تزال تعاني من تعقيد زمني قدره O(n²) بسبب الحلقات المتداخلة.

public class RemoveDuplicates {

    public static int[] removeDuplicatesIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        int index = 1; 
        for (int i = 1; i < arr.length; i++) {
            boolean isDuplicate = false;
            for (int j = 0; j < index; j++) {
                if (arr[i] == arr[j]) {
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {
                arr[index++] = arr[i];
            }
        }
        return Arrays.copyOf(arr, index);
    }
    //main method remains the same as above
}

التعقيد الزمني: O(n²)
التعقيد المكاني: O(1)

استخدام طريقة Arrays.sort()

يستخدم هذا النهج وظيفة الفرز المدمجة في جافا. يُجمع فرز المصفوفة أولاً العناصر المكررة معًا. تمريرة واحدة لاحقة عبر المصفوفة المُرتبة تحدد وتحتفظ فقط بالحدوث الأول لكل عنصر. يُسيطر التعقيد الزمني على خوارزمية الفرز (O(n log n))، مما يوفر أداءً أفضل بكثير لمجموعات البيانات الأكبر حجمًا من الطرق السابقة.

import java.util.Arrays;

public class RemoveDuplicates {

    public static int[] removeDuplicatesSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        Arrays.sort(arr); 
        int[] uniqueArr = new int[arr.length];
        uniqueArr[0] = arr[0]; 
        int uniqueCount = 1;

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[i - 1]) {
                uniqueArr[uniqueCount++] = arr[i];
            }
        }

        return Arrays.copyOf(uniqueArr, uniqueCount);
    }
    //main method remains the same as above
}

التعقيد الزمني: O(n log n)
التعقيد المكاني: O(n)

مقارنة الطرق

يعتمد اختيار الطريقة على حجم بياناتك وأولوياتك. بالنسبة للمصفوفات الأصغر حجمًا، قد تكفي بساطة طريقة المصفوفة المؤقتة. بالنسبة للمصفوفات الأكبر حجمًا، تفوق مكاسب الأداء لطريقة Arrays.sort() تعقيدها المكاني الأعلى قليلاً. توفر طريقة المؤشر المنفصل حلًا فعالاً من حيث استخدام المساحة، لكن تعقيدها الزمني التربيعي يجعلها أقل جاذبية لمجموعات البيانات الكبيرة.