연속 된 두 개의 동일한 값을 큰 값으로 대체


난이도 쉽게
자주 묻는 질문 Accenture FreeCharge 페이팔 사각형. 테라 데이타
배열

문제 정책

정수가 있다고 가정하십시오. 정렬. "두 개의 연속 된 동일한 값을 하나 더 큰 값으로 바꾸기"문제는 모든 쌍 값을 "a"라고 말하며 연속적으로 그들보다 큰 숫자 "a + 1"1 (두 개의 연속 된 숫자)로 바꾸도록 요청합니다. 또는 반복은 새로운 연속 쌍이 남아 있지 않습니다.

arr[]={5, 2, 1, 1, 2, 2}
5 4

설명

1은 연속 된 숫자이므로 2보다 큰 값으로 대체되고 arr은 {5,2,2,2,2}가됩니다.

이제 2는 연속 된 숫자이므로 그보다 큰 숫자로 대체됩니다. 즉, 3과 arr은 {5,3,2,2}가됩니다.

다시 2는 연속 된 숫자이므로 3으로 대체되고 arr은 {5,3,3}이됩니다.

이제 3은 연속 번호이므로 4로 대체되고 arr은 {5,4}가됩니다.

arr[]={2,5,5,6,2,7,7}
2 7 2 8

설명

5는 연속 된 숫자이므로 1을 의미하는 것보다 큰 값 6로 대체됩니다. 따라서 arr은 arr [] = {2,6,6,2,7,7}과 같습니다.

6 대신 6이 나오지만 다음 숫자도 1이므로 6보다 큰 값 7로 대체됩니다. 이는 2,7,2,7,7을 의미하고 arr은 {XNUMX}이됩니다.

7도 연속적으로 발생하므로 8로 대체되고 arr은 {2,7,2,8}이됩니다.

암호알고리즘

1. Set the position’s value to 0.
2. Traverse the array from o to n(n is the length of the array).
  1. Copy the value of arr[i] to arr[position] and increase the value of the position by 1.
  2. While the position is greater than 1, its previous two values are equal or not.
    1. Decrease the value of a position by 1,
    2. and increase the value of arr[position -1] by 1.
3. Print the array from index 0 to position.

설명

우리는 정렬 of 정수. 연속적으로 오는 모든 값을 숫자 자체보다 큰 숫자 1로 바꾸도록 요청했습니다. 4가 연속적으로 배열에 들어 오면 값 5로 대체됩니다. 이는 숫자 1보다 4이 더 큽니다. 이제 한 번의 순회로만 수정할 수 있습니다. 3, 4, 4에 5 개의 숫자가 있다고 가정합니다. 그러면 4, 4를 5로 변환하고 5는 연속 된 숫자입니다. 다음 숫자는 숫자 자체와 동일하기 때문입니다. 따라서 중첩 루프를 사용하여이 작업을 수행합니다.

0에서 n까지 배열을 이동합니다. 루프를 열면 중첩 루프가됩니다. 외부 루프를 사용하여 순회를 처리합니다. 내부 루프를 사용하여 주어진 조건에 따라 값을 업데이트하거나 값을 대체합니다. 외부 루프에서 동일한 배열의 값을 최대 XNUMX 개까지 복사합니다.

외부 루프에서 두 번의 순회 후에 만 ​​내부 루프로 이동합니다. 안에 while 루프, 우리는 인덱스 값이 1보다 큰지 확인할 것입니다. 이전 두 값이 같은지 비교할 것이기 때문입니다. 그렇기 때문에 두 값을 배열 위치 값에 복사해야한다는 조건을 그대로 둡니다. 그런 다음 단순히 위치 값을 줄이고 숫자 자체보다 큰 값 1로 배열 요소를 업데이트하십시오. 이 루프와이 방법을 계속 사용하겠습니다. 모든 값을 연속 된 값으로 지속적으로 대체합니다.

이제 0에서 마지막으로 업데이트 된 인덱스 위치까지 배열을 인쇄하면 원하는 배열이 제공됩니다.

연속 된 두 개의 동일한 값을 큰 값으로 대체

 

암호

두 개의 연속 된 동일한 값을 더 큰 값으로 바꾸는 C ++ 코드

#include<iostream>

using namespace std;

void replaceValues(int arr[], int n)
{
    int position = 0;

    for (int i = 0; i < n; i++)
    {
        arr[position++] = arr[i];
        while (position > 1 && arr[position - 2] == arr[position - 1])
        {
            position--;
            arr[position - 1]++;
        }
    }
    for (int i = 0; i < position; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 2,5,5,6,2,7,7};
    int n = sizeof(arr) / sizeof(int);
    replaceValues(arr, n);
    return 0;
}
2 7 2 8

두 개의 연속적인 동일한 값을 더 큰 값으로 바꾸는 Java 코드

class replaceConsecutiveValues
{
    public static void replaceValues(int arr[], int n)
    {
        int position = 0;
        for (int i = 0; i < n; i++)
        {
            arr[position++] = arr[i];
            while (position > 1 && arr[position - 2] == arr[position - 1])
            {
                position--;
                arr[position - 1]++;
            }
        }
        for (int i = 0; i < position; i++)
            System.out.print( arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = {2,5,5,6,2,7,7};
        int n = arr.length;
        replaceValues (arr, n);
    }
}
2 7 2 8

복잡성 분석

시간 복잡성

의 위에2어디에"엔" 배열의 요소 수입니다.. 알고리즘이 다항식 시간에 실행되도록 만든 두 개의 중첩 루프를 사용했기 때문입니다.

공간 복잡성

O (1), 배열의 요소 수와 무관합니다.. 알고리즘 자체는 일정한 공간을 차지하지만 프로그램은 전체적으로 O (N) 공간 (입력 용)을 사용합니다.