주어진 범위를 중심으로 배열의 XNUMX 방향 분할


난이도 쉽게
자주 묻는 질문 은행 바자 BlackRock 자본 하나 문 프로그 연구소 Synopsys Twilio Yahoo
배열

문제 정책

당신은 주어진 정렬 of 정수 lowValue 및 highValue 범위가 있습니다. “주어진 범위를 중심으로 한 배열의 XNUMX 방향 분할”문제는 배열이 세 부분으로 나뉘도록 배열을 분할하도록 요구합니다. 배열의 파티션은 다음과 같습니다.

  1. 첫 번째 파티션의 요소는 lowValue보다 작습니다.
  2. 요소가 주어진 범위 내에있는 다음 파티션은이 파티션에 있고
  3. highValue보다 큰 숫자는 배열의 세 번째 파티션이됩니다.

arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30
2 5 1 12 4 9 23 76 56 45 87

설명

lowValue는 15이므로 왼쪽의 숫자는 lowValue보다 작습니다.

범위는 15에서 30 사이이며 23은이 범위 사이에있는 숫자입니다.

highValue는 30이고 highValue보다 큰 숫자는 모두 오른쪽에 있습니다.

주어진 범위를 중심으로 배열의 XNUMX 방향 분할

암호알고리즘

1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
    1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
    2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
    3. Else increase the value of i by 1.
3. Print the array.

설명

정수 배열과 lowValue 및 highValue 범위를 지정했습니다. 배열을 배열하거나 배열을 분할해야합니다. lowValue보다 작은 배열의 가능한 모든 수가 배열의 왼쪽에 있도록합니다. 그리고 배열의 범위 사이에있는 배열의 번호는 배열에서 다음이됩니다. 그리고 다음 값은 highValue보다 큰 숫자가 마지막이됩니다.

0부터 배열을 순회 할 것입니다.th 마지막 색인에 대한 색인. 그러나 그 전에 우리는 변수를 선언하고 배열의 0과 마지막 인덱스로 초기화했습니다. lowValue보다 낮은 값이 발견 될 때마다 스와핑시, startingValue에서 연산이 수행되고 highValue보다 큰 값이 발견 될 때마다 endingValue에서 연산이 수행됩니다. 배열을 순회하고 현재 배열 요소가 true 인 경우 주어진 lowValue보다 작은 지 확인한 다음 배열의 현재 값과 배열의 첫 번째 위치 값을 바꿉니다. 이 값은 시작점을 추적하고 다른 값은 요소를 교체하기 위해 끝 인덱스를 추적합니다. 요소가 현재 배열 요소의 값보다 큰 경우 다른 교체가 수행됩니다. 그런 다음 요소가 현재 요소와 교체되는 인덱스 인 endingValue가 나옵니다. 어떤 조건도 만족하지 않으면 숫자가 주어진 범위 내에 있다는 것을 의미하면 변경하지 않습니다. 순회가 완료되면 원하는 배열을 갖게됩니다. 배열을 인쇄하기 만하면됩니다.

암호

주어진 범위 주변에서 배열의 XNUMX 방향 분할을 해결하는 C ++ 코드

#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int startingValue = 0, endingValue = n-1;

    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[startingValue++]);

        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);

        else
            i++;
    }
}

int main()
{
    int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 15, 30);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
2 5 1 12 4 9 23 76 56 45 87

주어진 범위 주변에서 배열의 XNUMX 방향 분할을 해결하기위한 Java 코드

class ThreeWayPartition
{
    public static void getPartition(int[] arr, int lowValue, int highValue)
    {
        int n = arr.length;

        int startingValue = 0, endingValue = n-1;

        for(int i = 0; i <= endingValue;)
        {
            if(arr[i] < lowValue)
            {

                int temp = arr[startingValue];
                arr[startingValue] = arr[i];
                arr[i] = temp;
                startingValue++;
                i++;
            }
            else if(arr[i] > highValue)
            {

                int temp = arr[endingValue];
                arr[endingValue] = arr[i];
                arr[i] = temp;
                endingValue --;
            }
            else
                i++;
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

        getPartition(arr, 15, 30 );

        for (int i=0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");

        }
    }
}
2 5 1 12 4 9 23 76 56 45 87

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 배열 요소를 순회했기 때문에 시간 복잡도는 선형입니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다. 알고리즘 자체는 내부 알고리즘이며 주어진 초기 배열을 업데이트합니다. 따라서 알고리즘의 공간 복잡성은 일정하지만 프로그램은 선형입니다.