將所有負元素移動到最後,並留出額外的空間  


難度級別 容易獎學金
經常問 第一資本 思傑 IBM SAP實驗室 出租車 Twilio
排列

問題陳述  

“將所有負元素按順序移動,並在末尾留有多餘的空間”指出,您將獲得一個同時包含正數和負數的數組。 問題語句要求將所有否定元素移到數組的最後。

例  

arr[] = { 1,2,-3,-5,2,7,-9,-11 }
1, 2, 2, 7, -3, -5, -9, -11
說明:所有負值均已移至數組的最後一個。 而且它們也處於初始順序。

將所有負元素按順序移到最後的算法,並留出額外的空間  

1. Declare an array same as the size of the original array.
2. Traverse the array and check if any number is greater than or equal to 0,
    1. If true then copy that number from the 0th position of the array we created.
3. Now traverse the array and check if any of the numbers is less than 0.
    1. If true, then copy that value to the array we created from the next position where the positive number ends.
4. Now copy that temporary array we created into the original array and print that array.

解釋

我們得到了一個 整數 同時包含負數和正數的數組。 我們已經要求以重新排列數組的方式將所有負元素移到數組的最後/結尾。 然後,我們將分別遍歷正負元素的數組。 首先,我們必須對肯定元素執行操作,然後將它們向左拉。 然後將所有否定元素向右移動。

也可以看看
序列中第二重複的單詞

我們必須創建一個與原始數組大小相同的額外數組。 因為這樣,我們將存儲所需的數字排列。 選取一個變量索引並將其初始化為0。此變量將幫助我們區分正數元素和負數元素。 現在,我們創建了一個數組。 我們將從原始數組到臨時數組中放入正數。

我們將在遍歷時檢查數組元素是否大於或等於0,然後僅從臨時數組的起始位置將該元素複製到臨時數組中。 同樣,我們同時增加索引值,因此,由於我們上次復制正值元素,因此自下一個元素起我們就有一個值索引要存儲在其中,借助於此,我們將最後推送所有負值元素。

現在,我們將再次遍歷該數組,並檢查每個元素是否小於0(如果為零),然後開始從我們離開的索引值將該值推入臨時數組。 最後,將該陣列複製到原始陣列,然後進行打印,或者僅打印臨時陣列,兩者都是相同的。 然後我們得到所需的輸出。

將所有負元素移動到最後,並留出額外的空間

推薦碼  

C ++代碼將所有否定元素按順序移到末尾,並留有多餘的空間

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

void segregateElements(int arr[], int n)
{
    int temp[n];

    int j = 0;

    for (int i = 0; i < n ; i++)
        if (arr[i] >= 0 )
            temp[j++] = arr[i];

    if (j == n || j == 0)
        return;

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

    memcpy(arr, temp, sizeof(temp));
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
    int n = sizeof(arr)/sizeof(arr[0]);

    segregateElements(arr, n);
    printArray(arr,n);

    return 0;
}
1 2 2 7 -3 -5 -9 -11

Java代碼將所有否定元素按順序移動到末尾,並留有額外的空間

import java.util.Arrays;

class moveNegativeElement
{
    public static void segregateElements(int arr[], int n)
    {
        int temp[] = new int[n];

        int j = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] >= 0)
                temp[j++] = arr[i];

        if (j == n || j == 0)
            return;

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

        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }
    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 arg[])
    {
        int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
        int n = arr.length;

        segregateElements(arr, n);
        printArray(arr,n);

    }
}
1 2 2 7 -3 -5 -9 -11

複雜度分析  

時間複雜度

上) 哪裡 “ N” 是數組中元素的。 我們僅遍歷了數組,從而實現了線性時間複雜度。

也可以看看
在給定範圍內對數組進行三向分區

空間複雜度

上) 哪裡 “ N” 是數組中元素的。 我們創建了一個臨時使用的額外數組,在其中我們以所需的方式存儲了元素。