첫 번째 요소를 두 배로 늘리고 XNUMX을 끝까지 이동

난이도 중급
자주 묻는 질문 Microsoft 조호 (Zoho)
배열조회수 25

문제 정책

배열이 있다고 가정합니다. 정수. 여기서 "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으로 업데이트합니다. 배열의 모든 값에 대해이 작업을 수행해야합니다.

이제 모든 값을 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

복잡성 분석

시간 복잡성

의 위에) 어디에 "엔" 배열의 요소 수입니다. 우리는 단순히 배열을 두 번 탐색하여 알고리즘이 선형 시간으로 실행되도록했습니다.

공간 복잡성

알고리즘에는 O (1) 추가 공간이 있지만 프로그램은 입력을 저장하는 데 O (N) 총 공간을 사용합니다.

Translate »