在給定範圍內對數組進行三向分區


難度級別 容易獎學金
經常問 銀行集市 貝萊德 第一資本 堡壘 月蛙實驗室 新思 Twilio 雅虎
排列

問題陳述

給你一個 排列 of 整數 以及一系列lowValue和highValue。 問題“在給定範圍內對數組進行三向分割”要求對數組進行分割,以便將數組分為三部分。 數組的分區將是:

  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的數字都將在右側。

在給定範圍內對數組進行三向分區

算法

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處執行操作。 我們將遍歷數組,並檢查當前數組元素是否小於給定的lowValue(如果為true),然後交換數組的當前值和數組的第一個位置值。 這個值我們將跟踪起始點,其他值將跟踪結束索引以交換元素,如果發現該元素大於當前數組元素的值,則將進行另一次交換。 然後是endingValue,該元素與當前元素交換處的索引。 如果沒有一個條件滿足,則意味著該數字在給定範圍內,那麼我們不會對其進行更改。 遍歷完成後,我們有了所需的數組。 我們只需要打印數組。

推薦碼

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

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) 哪裡 “ n” 是數組中元素的數量。 由於我們遍歷了數組元素,因此時間複雜度是線性的。

空間複雜度

O(1) 因為不需要額外的空間。 該算法本身是就地算法,並且正在更新初始給定數組。 因此,算法的空間複雜度是恆定的,而程序是線性的。