最初の要素をXNUMX倍にし、ゼロを最後まで移動します


難易度 ミディアム
よく聞かれる マイクロソフト Zohoの
配列

問題文

あなたがの配列を持っていると仮定します 整数。 ここで、「0」は入力と見なされる数値ではありません。 ここでは有効な入力ではありません。 「最初の要素を0倍にし、ゼロを最後まで移動する」という問題は、0以外の数が見つかり、その次の数が同じ数である場合に、その数をXNUMX倍にして、次の数値はXNUMXです。最後にすべてのゼロを最後に押します。

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

説明:3は連続して発生する数なので、最初に3を6倍にして3にし、次の0をXNUMXとしてマークします。また、すべてのゼロがlast.xにシフトされました。

最初の要素をXNUMX倍にし、ゼロを最後まで移動するためのアルゴリズム

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倍にする必要があることです。 そして、与えられた条件が満たされる場合、次の番号をXNUMXとしてマークします。 この変更後、作成した配列の最後のゼロ、または配列にすでに存在するすべてのゼロをシフトする必要があります。 その後、出力が返されることになっています。

配列を0からn–1までトラバースします。各値が0に等しくないかどうかを確認します。0の値を変更することは許可されていないためです。 そして、現在の要素が次の要素と等しいかどうかをarr [i] = = arr [i +1]として確認します。 現在の番号の次の番号を検索しているため、トラバースの最後のポイントとしてn-1を使用しました。 したがって、検索する最後の要素としてnを選択すると、nullポインター例外が発生します。 指定された条件が満たされた場合、現在の要素を選択して現在の値の0倍にし、次の値をXNUMXに更新します。配列のすべての値に対してこれを行う必要があります。

ここで、すべての値を0として最後にシフトします。 このために、配列を再度トラバースし、値が等しくないかどうかを確認してから、左にシフトします。すべての値を左にシフトした後、最後にシフトされた値のインデックスがあります。そのカウントから、ループし、そのカウントからnの値まで、すべての値を0として更新します。最後に配列を出力します。

最初の要素をXNUMX倍にし、ゼロを最後まで移動します

コード

最初の要素をXNUMX倍にし、問題を終了するためにゼロを移動するための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

最初の要素をXNUMX倍にし、問題を終了するためにゼロを移動するためのJavaコード

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

複雑さの分析

時間の複雑さ

オン) where "N" 配列内の要素の数です。 配列をXNUMX回トラバースしただけで、アルゴリズムは線形時間で実行されます。

スペースの複雑さ

アルゴリズムには O(1) 余分なスペースがありますが、プログラムは入力を格納するためにO(N)の合計スペースを取ります。