Перамясціце ўсе адмоўныя лічбы на пачатак і станоўчыя, каб скончыць пастаянным дадатковым прабелам


Узровень складанасці Лёгка
Часта пытаюцца ў Capgemini Паход MAQ o9 рашэнні TCS
масіў сартаванне

Дапусцім, у вас ёсць масіў цэлых лікаў. Ён складаецца як з адмоўных, так і з дадатных лікаў, і ў пастаноўцы задачы просяць перанесці / перамясціць усе адмоўныя і дадатныя элементы злева ад масіва і справа ад масіва, не выкарыстоўваючы лішняга прасторы. Гэта будзе рашэнне для перамяшчэння ўсіх адмоўных лікаў да пачатку і дадатнага да канца з пастаяннай дадатковай прасторай.

Прыклад

 Уваход:

arr[]={2,4,-10,13,-7,-60,52,8,-19 }

Вынахад:

-10 -7 -60 -19 4 2 52 8 13

Тлумачэнне: Паколькі ўсе лічбы зрушаны ўлева, а ўсе дадатныя - управа.

Перамясціце ўсе адмоўныя лічбы на пачатак і станоўчыя, каб скончыць пастаянным дадатковым прабелам

Алгарытм

  1. Усталюйце j на 0.
  2. Пераход па масіве ад 0 да n (выключна, дзе n - даўжыня масіва).
    1. Праверце, калі які-небудзь элемент масіва менш за 0,
      1. Праверце, ці павінен я быць роўным j,
        1. Памяняйце месцамі значэнні індэксаў arr [i] і arr [j] і павялічце значэнне j.
  3. Раздрукаваць масіў.

Тлумачэнне для перамяшчэння ўсіх адмоўных лікаў у пачатак і станоўчага ў канец

Нам даецца масіў цэлых лікаў, і масіў змяшчае станоўчыя і адмоўныя элементы. Мы папрасілі зрушыць усе адмоўныя элементы ўлева і дадатныя лікі ўправа. Дзеля гэтага мы і збіраемся абмен усе лікі, якія з'яўляюцца станоўчымі і адмоўнымі элементамі. Спачатку перабярыце масіў, а потым праверце наяўнасць адмоўных лікаў, калі лік адмоўны, то толькі мы пойдзем на падмену значэнняў.

Усталюйце значэнне j на 0, яно будзе выкарыстоўвацца для альтэрнатыўнага значэння, якое трэба памяняць. Мы пачнем абход масіва і праверым для кожнага ліку, бо arr [i] менш за 0, калі менш за 0, значыць, мы знайшлі адмоўнае лік, і таму мы праверым, ці не супадаюць абодва індэкса, гэта ўсе вышэйпералічаныя ўмовы адпавядаюць рэчаіснасці, тады мы памяняем лічбы, паколькі arr [i] і arr [j] памяняем месцамі, і павялічым значэнне j. мы будзем працягваць гэты ход, пакуль усе магчымыя значэнні не будуць пройдзены, заменены і перастаўлены ў адпаведнасці з дадзенай умовай.

Мы праверылі, што ўмова arr [i] менш за 0, таму што мы проста размяшчаем адмоўныя лікі, усе адмоўныя лікі пасля замены размяшчаюцца злева ад масіва, а ўсе астатнія дадатныя лікі размяшчаюцца аўтаматычна справа масіва. Пасля ўсёй замены, якую мы зрабілі, нам проста трэба надрукаваць масіў, у якім выконваліся аперацыі замены.

Рэалізацыя

Праграма C ++ для перамяшчэння ўсіх адмоўных лікаў у пачатковы і станоўчы ў канец

#include<iostream>

using namespace std;

void shiftIntegers(int arr[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
        {
            if (i != j)
                swap(arr[i], arr[j]);
            j++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shiftIntegers(arr, n);

    return 0;
}
-10 -7 -60 -19 4 2 52 8 13

Праграма Java для перамяшчэння ўсіх адмоўных лікаў у пачатковы і станоўчы ў канец

class rearrangeNegativePositive
{
    public static void shiftIntegers(int arr[], int n)
    {
        int j = 0, temp;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] < 0)
            {
                if (i != j)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                j++;
            }
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
        int n = arr.length;

        shiftIntegers(arr, n);
        printArray(arr, n);
    }
}
-10 -7 -60 -19 4 2 52 8 13

Аналіз складанасці для перамяшчэння ўсіх адмоўных лікаў у пачатак і ў станоўчы канец

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

O (1) бо дадатковае месца не патрабуецца.

заключэнне

Гэта праграма для перамяшчэння ўсіх адмоўных лікаў у пачатак і ў станоўчы канец з пастаянным дадатковым прасторай у Java і C ++.

Спасылка