لومړی عنصر دوه ځله کړئ او صفر د پای ته حرکت ورکړئ


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي د Microsoft زو
پیشه

ستونزه بیان

فرض کړئ چې تاسو یو لړ لرئ ضمیمه. دلته "0" یوه شمیره نده چې د ان پټ په توګه ګ .ل کیږي. دا دلته د اعتبار وړ ندی. ستونزه "لومړی عنصر دوه ځله کړئ او صفر ته د پای ته تلل" پوښتنه کوي په داسې ډول د سرالي منظم کولو لپاره که چیرې د 0 څخه پرته نور شمیره وموندل شي او د هغه راتلونکي شمیره ورته شمیره وي ځکه چې بیا دا شمیره دوه چنده ده او په نښه شوی راتلونکی شمیره د 0 په څیر. په پای کې ټول صفر فشار ورکړئ.

بېلګه

arr[] = {3, 3, 5, 0, 1, 0, 0, 1, 0}
6 5 1 1 0 0 0 0 0

تشریح: له هغه وخته چې شمیره 3 ده چې په پرله پسې ډول پیښیږي ، نو موږ 3 لومړی دوه کړئ ترڅو دا 6 رامینځته کړئ او راتلونکی 3 په نښه کړئ 0 او همدارنګه ټول زیرو وروستي.x ته لیږدول شوي.

د لومړي عنصر ډبل کولو لپاره الګوریتم او پای ته د صفر حرکت

1. Traverse the array from 0 to n-1(inclusively).
2. Check if arr[i] is not equal to 0 and arr[i]==arr[i+1](next value is same as current value).
  1. If true, then make the current value twice of the self.
  2. Update next element as 0 and do i++.
3. Traverse the array from i = 0 to n-1(step of shifting all the zeroes to the end).
  1. Check if arr[i] != 0.
    1. Arr[count]=arr[i] and do count++.
4. From the traversal of till count is less than n.
  1. Arr[count]=0 and do count++.
5. Print the array.

تشریح

ورکړل شوي یو ترتیب یې په ورکړل شوي ب .ه سره تنظیم کړئ. موږ غوښتنه کړې چې راتلونکي شمیره بدله کړو که موجوده شمیره د بل شمیره ورته وي. بدلون دا دی چې موږ باید موجوده شمیره دوه چنده کړو. او راتلونکی شمیره په 0 نښه کړئ که ورکړل شوی شرایط خوښ شي. د دې ترمیم وروسته ، موږ باید ټول صفرونه د صف په وروستي برخه کې چې موږ جوړ کړي یا هغه څه چې دمخه په صف کې شتون لري ځای په ځای کړو. بیا به وتلی شي چې بیرته راستانه شي.

له 0 څخه تر n پورې - صف ته ځیر شئ - وګورئ چې هر یو د 1 ارزښت سره برابر نه دی ځکه چې موږ د 0 ارزښتونو کې هیڅ بدلون راوستو اجازه نلرو. او وګورئ چې ایا اوسنی عنصر د بل عنصر سره برابر دی لکه د آرر [i] = = آر آر [i + 0]. موږ د انټرنیټ د وروستي ټکي په توګه n-1 نیولی ځکه چې موږ اوسني شمیره ته راتلونکي شمیره لټون کوو. نو که موږ د وروستي عنصر په توګه وپلټل شي د n لپاره ځو ، موږ به د نول پوائنټر استثنا ترلاسه کړو. که ورکړل شوي شرایط مطمئن وي نو موږ اوسنی عنصر غوره کوو او دا د اوسني ارزښت دوه چنده کوو او راتلونکی ارزښت 1 ته تازه کوو. موږ باید دا د صفونو ټولو ارزښتونو لپاره وکړو.

اوس ټول ارزښتونه د 0 په توګه وروستي ته واړوئ. د دې لپاره بیا صف صفر کړئ ، او وګورئ چې که ارزښت مساوي نه وي ، بیا یې کی left لور ته واړوئ ، وروسته ټول ارزښتونه کی left اړخ ته لیږدولو سره ، موږ د وروستي لیږل شوي ارزښت شاخص لرو ، له هغه شمیرنې څخه به موږ یو لوپ او له هغه شمیر څخه د n ارزښت ته ، موږ به ټول ارزښتونه د 0 په توګه تازه کړو. په پای کې د سایټ چاپ.

لومړی عنصر دوه ځله کړئ او صفر د پای ته حرکت ورکړئ

کوډ

د لومړي عنصر دوه چنده کولو لپاره C ++ کوډ او د صفر ستونزه د پای ته رسیدو لپاره

#include<iostream>

using namespace std;

void shiftZeroAtLast(int arr[], int n)
{
    int count = 0;

    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i];

    while (count < n)
        arr[count++] = 0;
}
void arrayModification(int arr[], int n)
{
    if (n == 1)
        return;
    for (int i = 0; i < n - 1; i++)
    {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
        {
            arr[i] = 2 * arr[i];

            arr[i + 1] = 0;

            i++;
        }
    }
    shiftZeroAtLast(arr, n);
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {3,3,5,0,1,0,0,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    arrayModification(arr, n);

    cout << "Modified array: ";
    printArray(arr, n);

    return 0;
}
Modified array: 6 5 1 1 0 0 0 0 0

د لومړي عنصر دوه ځله لپاره د جاوا کوډ او د ستونزې پای ته د صفر حرکت

class arrayRearrange
{
    public static void shiftZeroAtLast(int arr[], int n)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] != 0)

                arr[count++] = arr[i];

        while (count < n)
            arr[count++] = 0;
    }
    public static void arrayModification(int arr[], int n)
    {
        if (n == 1)
            return;

        for (int i = 0; i < n - 1; i++)
        {
            if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
            {
                arr[i] = 2 * arr[i];

                arr[i + 1] = 0;

                i++;
            }
        }
        shiftZeroAtLast(arr, n);
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = {3,3,5,0,1,0,0,1,0};
        int n = arr.length;


        arrayModification(arr, n);

        System.out.print("Modified array: ");
        printArray(arr, n);
    }
}
Modified array: 6 5 1 1 0 0 0 0 0

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

د وخت پیچلتیا

O (N) هلته "N" په صف کې د عناصرو شمیر دی. موږ په ساده ډول دوه ځله سیر وستایه کوم چې الګوریتم په خطي وخت کې پرمخ وړي.

د ځای پیچلتیا

الګوریتم اړتیا لري O (1) اضافي ځای مګر برنامه آخذه ذخیره کولو لپاره O (N) ټوله ځای نیسي.