Array-da alternativ olaraq müsbət və mənfi nömrələri yenidən düzəldin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Bloomberg Capital One Cisco Facebook google Morgan Stanley Kahin VMware
GeyimBaxılıb 782

Problem bəyanat

“Alternativ olaraq Pozitiv və Mənfi Ədədləri Arrayda Yenidən Düzəldin” problemində bir array a []. Bu sıra müsbət və mənfi tam ədədlərdən ibarətdir. Dizini müsbət və mənfi alternativ olaraq yerləşdiriləcək şəkildə yenidən düzəldin. Burada müsbət və mənfi elementlərin sayı bərabər olmamalıdır.

Qeyd: Daha çox müsbət və ya mənfi element varsa, onlar massivin sonunda görünür.

Giriş Formatı

Bir tam ədədi olan ilk və yalnız bir sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

N boşluqla ayrılmış tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 5
  • -10 ^ 9 <= N <= 10 ^ 9

misal

7
-5 -7 9 11 12 -15 17
-5 11 -15 17 -7 12 9

Explanation: Alternativ mövqelərdə yenidən düzəldilmiş müsbət və mənfi cəhətlər və sonunda artıqlıq.

8
-4 -7 9 11 -16 13 3 -5
-16 11 -4 3 -7 13 -5 9

Explanation: Alternativ mövqelərdə yenidən pozitiv və mənfi.

Alqoritm

Burada bütün müsbətləri tək, indeksləri cüt göstəricilərdə yenidən düzəldirik. İzlədiyimiz alqoritm aşağıda yazılmışdır.

  1. Dizini elə düzəldirik ki, bütün müsbətlər massivin əvvəlində olacaq. Və sonunda bütün mənfi elementlər.
    [1, -2, 3, 4, 5, -6, 7, 8, -9] → [1, 3, 4, 5, 7, 8, -2, -6, -9]
  2. I və j iki göstəricisini saxlayırıq. Əgər massiv [j]> 0 olarsa, onu birinci elementlə mübadilə edərək massivin ön hissəsinə aparırıq. Əks təqdirdə irəliləyirik.
  3. Mənfi rəqəmləri başlanğıc göstəricisini 0 kimi mənfi və müsbət olaraq başlatırıq.
  4. Mənfi göstəricini 1, müsbət göstəricini 2 artırın. Yəni hər alternativ müsbət ədədi növbəti mənfi rəqəmlə dəyişdiririk.

Həyata keçirilməsi

Alternativ olaraq massivdə müsbət və mənfi nömrələri yenidən təşkil etmək üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;

//Rearrange function  
void Rearrange(int array[], int n)
{
    int i = -1;
    //swap positive elements to the start of the array
    for (int j = 0; j < n; j++)
    {
        if (array[j] > 0)
        {
            i = i + 1;
            swap(array[i], array[j]);
        }
    }
    //Initialize positive_index, negative_index
    int positive_index = 0, negative_index = i + 1;
    //Increment postive by 2 and negative by 1.
    //swap elements after each increments and swap them.
    //such that alternative elements will be changed
    while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
    {
        swap(array[negative_index], array[positive_index]);
        positive_index = positive_index + 2;
        negative_index = negative_index + 1;
    }
}
 
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    Rearrange(a,n);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

Alternativ olaraq massivdə müsbət və mənfi nömrələri yenidən təşkil etmək üçün Java proqramı

import java.util.Scanner;
class sum
{
    //Rearrange function  
    public static void Rearrange(int array[], int n)
    {
        int i = -1;
        //swap positive elements to the start of the array
        for (int j = 0; j < n; j++)
        {
            if (array[j] > 0)
            {
                i = i + 1;
                array[i] = (array[i] + array[j]) - (array[j] = array[i]);
            }
        }
        //Initialize positive_index, negative_index
        int positive_index = 0, negative_index = i + 1;
        //Increment postive by 2 and negative by 1.
        //swap elements after each increments and swap them.
        //such that alternative elements will be changed
        while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
        {
            array[negative_index] = (array[negative_index] + array[positive_index]) - (array[positive_index] = array[negative_index]);
            positive_index = positive_index + 2;
            negative_index = negative_index + 1;
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Rearrange(a, n);
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
    }
}
5
-1 -2 -3 4 5
-3 5 -1 4 -2

Arrayda Alternativ olaraq Müsbət və Mənfi Ədədlərin Yenidən Düzəldilməsi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada sadəcə bütün massivi gəzirik və daimi vaxt tələb edən bəzi əməliyyatları yerinə yetiririk.

Kosmik Mürəkkəblik

O (1) çünki burada sadəcə elementlərin mövqelərini dəyişdirdik. Heç bir köməkçi yerdən istifadə etmirik.

Translate »