Удвойте первый элемент и переместите ноль в конец


Сложный уровень средний
Часто спрашивают в Microsoft Zoho
массив

Постановка задачи

Предположим, у вас есть массив целые. Здесь «0» не является числом, которое считается вводом. Здесь недопустимый ввод. Задача «Удвойте первый элемент и переместите ноль в конец» просит переставить массив таким образом, если будет найдено число, отличное от 0, и следующее число будет таким же, как и оно, тогда удвоить число и пометить следующее число как 0. Наконец, нажмите все нули в конце.

Пример

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

Объяснение: Поскольку 3 - это число, которое встречается последовательно, поэтому мы сначала удваиваем 3, чтобы получилось 6, и помечаем следующие 3 как 0. А также все нули были сдвинуты на last.x

Алгоритм удвоения первого элемента и перемещения нуля в конец

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, если данное условие удовлетворяет. После этой модификации мы должны сдвинуть все нули в последнюю часть массива, который мы создали или который уже присутствует в массиве. Затем предполагается, что результат будет возвращен.

Пройдите по массиву от 0 до n - 1. Проверьте, не равно ли каждое из значений 0. Потому что нам не разрешено вносить какие-либо изменения в значения 0. И проверьте, равен ли текущий элемент следующему элементу, как arr [i] = = arr [i + 1]. Мы взяли n-1 в качестве последней точки обхода, потому что мы ищем следующее число к текущему числу. Итак, если мы выберем n в качестве последнего элемента, который будет искать, мы получим исключение нулевого указателя. Если данные условия выполнены, мы выбираем текущий элемент, удваиваем его по сравнению с текущим значением и обновляем следующее значение до 0. Мы должны сделать это для всех значений массива.

Теперь сдвиньте все значения как 0 на последнее. Для этого снова пройдитесь по массиву и проверьте, не равно ли значение, затем сдвиньте его влево, после сдвига всех значений влево у нас есть индекс последнего сдвинутого значения, из этого счетчика мы будем идти для цикл и от этого счетчика до значения n, мы обновим все значения как 0. Наконец, распечатайте массив.

Удвойте первый элемент и переместите ноль в конец

Код:

Код 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

Код 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

Анализ сложности

Сложность времени

НА) в котором "N", - количество элементов в массиве. Мы просто дважды прошли массив, что заставляет алгоритм работать в линейном времени.

Космическая сложность

Алгоритм требует O (1) дополнительное пространство, но программа занимает O (N) общего пространства для хранения ввода.