استبدل قيمتين متساويتين متتاليتين بقيمتين أكبر


مستوى الصعوبة سهل
كثيرا ما يطلب في اكسنتشر قلعة شحن مجاني Paypal مربع مقاومه
مجموعة

المشكلة بيان

افترض أن لديك عددًا صحيحًا مجموعة. تتطلب المشكلة "استبدل قيمتين متساويتين متتاليتين بأخرى أكبر" استبدال جميع قيم الأزواج هذه ، والتي تأتي على التوالي برقم "a + 1" 1 أكبر منهم (رقمان متتاليان) ، بحيث أنه حتى بعد التعديل أو التكرار لن يكون هناك زوج متتالي جديد متبقي.

مثال

arr[]={5, 2, 1, 1, 2, 2}
5 4

تفسير

نظرًا لأن 1 رقم متتالي ، يتم استبداله بقيمة أكبر من ذلك يعني 2 وسيصبح arr {5,2,2,2,2،XNUMX،XNUMX،XNUMX،XNUMX}

الآن 2 هو رقم متتالي ، لذلك سيتم استبداله برقم أكبر منه ، أي 3 وسيصبح arr {5,3,2,2،XNUMX،XNUMX،XNUMX}

مرة أخرى ، 2 هو رقم متتالي ، لذا سيتم استبداله بالرقم 3 وسيصبح arr {5,3,3،XNUMX،XNUMX}

الآن 3 هو الرقم المتتالي ، لذا سيتم استبداله بالرقم 4 وسيصبح arr {5,4،XNUMX}

arr[]={2,5,5,6,2,7,7}
2 7 2 8

تفسير

نظرًا لأن الرقم 5 هو رقم متتالي ، يتم استبداله بقيمة 1 أكبر من ذلك يعني 6. لذا ستبدو arr مثل arr [] = {2,6,6,2,7,7،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

يأتي الرقم 6 بدلاً من ذلك ولكن الرقم التالي هو أيضًا 6 ، لذلك يتم استبداله أيضًا بالقيمة 1 أكبر من 6 ، يعني 7 وسيصبح arr {2,7,2,7,7،XNUMX،XNUMX،XNUMX،XNUMX}

نظرًا لأن الرقم 7 يحدث بشكل متتالي أخيرًا ، لذلك يتم استبداله بالرقم 8 وسيصبح arr {2,7,2,8،XNUMX،XNUMX،XNUMX}

خوارزمية

1. Set the position’s value to 0.
2. Traverse the array from o to n(n is the length of the array).
  1. Copy the value of arr[i] to arr[position] and increase the value of the position by 1.
  2. While the position is greater than 1, its previous two values are equal or not.
    1. Decrease the value of a position by 1,
    2. and increase the value of arr[position -1] by 1.
3. Print the array from index 0 to position.

تفسير

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

اجتياز المصفوفة من 0 إلى n. افتح حلقة ، بحيث تصبح حلقة متداخلة. مع الحلقة الخارجية ، سنتعامل مع عمليات الاجتياز. وباستخدام الحلقة الداخلية ، سنقوم بتحديث القيم أو استبدال القيم وفقًا للحالة المحددة. في الحلقة الخارجية ، سنقوم بنسخ القيم في نفس المصفوفة حتى قيمتين.

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

الآن قم بطباعة المصفوفة من 0 إلى موضع الفهرس الذي تم تحديثه آخر مرة ، وسوف تعطي المصفوفة المطلوبة.

استبدل قيمتين متساويتين متتاليتين بقيمتين أكبر

 

رمز

كود C ++ لاستبدال قيمتين متساويتين متتاليتين بقيمتين أكبر

#include<iostream>

using namespace std;

void replaceValues(int arr[], int n)
{
    int position = 0;

    for (int i = 0; i < n; i++)
    {
        arr[position++] = arr[i];
        while (position > 1 && arr[position - 2] == arr[position - 1])
        {
            position--;
            arr[position - 1]++;
        }
    }
    for (int i = 0; i < position; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 2,5,5,6,2,7,7};
    int n = sizeof(arr) / sizeof(int);
    replaceValues(arr, n);
    return 0;
}
2 7 2 8

كود Java لاستبدال قيمتين متساويتين متتاليتين بقيمتين أكبر

class replaceConsecutiveValues
{
    public static void replaceValues(int arr[], int n)
    {
        int position = 0;
        for (int i = 0; i < n; i++)
        {
            arr[position++] = arr[i];
            while (position > 1 && arr[position - 2] == arr[position - 1])
            {
                position--;
                arr[position - 1]++;
            }
        }
        for (int i = 0; i < position; i++)
            System.out.print( arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = {2,5,5,6,2,7,7};
        int n = arr.length;
        replaceValues (arr, n);
    }
}
2 7 2 8

تحليل التعقيد

تعقيد الوقت

على2أين"ن" هو عدد العناصر في المصفوفة. لأننا استخدمنا حلقتين متداخلتين مما جعل الخوارزمية تعمل في وقت متعدد الحدود.

تعقيد الفضاء

يا (1) ، هذا مستقل عن عدد العناصر في المصفوفة. تأخذ الخوارزمية نفسها مساحة ثابتة ولكن البرنامج ككل يأخذ مساحة O (N) (للإدخال).