將所有負數移動到開頭,並以恆定的多餘空間將其移動到結尾  


難度級別 容易獎學金
經常問 凱捷 遠足 空氣質量 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(N) 哪裡 “ n” 是數組中元素的數量。

也可以看看
使用交易費用Leetcode解決方案買賣股票的最佳時間

空間複雜度

O(1) 因為不需要額外的空間。

結論  

這是一個在 Java 和 C++ 中將所有負數移動到開頭和正數到結尾的程序,並帶有恆定的額外空間。

參考文獻