在線性時間內找到大小為3的排序子序列


難度級別
經常問 Avalara 第一資本 堡壘 思傑 易趣 新思
排列

問題陳述

問題“在線性時間內找到大小為3的排序子序列”表明您有一個 整數 排列。 問題陳述要求找出三個數字,使得array [i] <array [k] <array [k],而i <j <k。

arr[] = {11,34,2,5,1,7,4 }
2 5 7

解釋

2小於5,5小於7,因此它們的索引彼此小於。

算法

1. Declare a new array “small” and “great” of size as same as the original array.
2. Set the value of maximum to n-1, and the value of minimum to 0.
3. Marked the first element of the array we created to -1.
4. Traverse the array from i=1 to less than n(n is the length of the array).
  1. Check if arr[i] is smaller or equal to arr[minimum], if true
    1. Set minimum to i and small[i] to -1.
  2. Else put small[i] = minimum.
5. Traverse the array from i=n-2 to less than equal to 0(n is the length of the array).
  1. Check if arr[i] is greater than or equal to arr[maximum], if true
    1. Set maximum to i and great[i] to -1.
  2. Else put great[i] = maximum.
6. Traverse the array from i=0 to n and check if small[i] and great[i] is not equal to -1, then print the arr[small[i]] , arr[i] and arr[great[i]].
  1. Return

解釋

我們有一個 排列 of 整數。 我們已要求找出 分類 給定數組中的子序列。 排序後的子序列包含三個我們必須按排序順序找到的數字,它應該按順序(不是連續的而是按順序)找到,第一個數字應小於第二個數字,第二個數字應小於第三個數字,並且第一個,第二和第三應該有序。

我們將遍歷數組從1到小於n,我們將第一個和最後一個索引元素保持原樣。 因為我們已經在創建的兩個數組中將它們標記為-1(小和大)。 我們標記了它們的first和index元素分別等於小數組和大數組的-1。 遍歷數組並檢查arr [i]是否小於或等於arr [minimum],其中最小值我們標記為0,如果發現條件為true,則將minimum的值更新為i,並標記為當前的小數組元素為-1。

對於大型數組,我們將執行相同的操作,但是從右側的第二個元素到數組的遍歷到0。我們將遍歷數組,並檢查arr [i]是否大於或等於arr [maximum ],如果為true,則必須將max的值更新為0,將great [i]的值更新為-1。 否則,我們將最大值設為[i]。 此後,我們將再次遍歷數組,並檢查small [i]和great [i]是否不等於-1,如果為true,則打印提及的值。

在線性時間內找到大小為3的排序子序列

 

推薦碼

C ++代碼在線性時間中找到大小為3的排序子序列

#include<iostream>
using namespace std;

void getTriplet(int arr[], int n)
{
    int maximum = n - 1;
    int minimum = 0;
    int i;

    int* small = new int[n];

    small[0] = -1;
    for (i = 1; i < n; i++)
    {
        if (arr[i] <= arr[minimum])
        {
            minimum = i;
            small[i] = -1;
        }
        else
            small[i] = minimum;
    }

    int* great = new int[n];

    great[n - 1] = -1;
    for (i = n - 2; i >= 0; i--)
    {
        if (arr[i] >= arr[maximum])
        {
            maximum = i;
            great[i] = -1;
        }
        else
            great[i] = maximum;
    }

    for (i = 0; i < n; i++)
    {
        if (small[i] != -1 && great[i] != -1)
        {
            cout << arr[small[i]] << " " << arr[i] << " "<< arr[great[i]];
            return;
        }
    }

    cout << "3 numbers not found";

    delete[] small;
    delete[] great;

    return;
}
int main()
{
    int arr[] = { 11,34,2,5,1,7,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getTriplet(arr, n);
    return 0;
}
2 5 7

Java代碼以線性時間查找大小為3的排序子序列

class SortedSubsequenceSize3
{
    public static void getTriplet(int arr[])
    {
        int n = arr.length;
        int maximum = n - 1;

        int minimum = 0;
        int i;

        int[] small = new int[n];

        small[0] = -1;
        for (i = 1; i < n; i++)
        {
            if (arr[i] <= arr[minimum])
            {
                minimum = i;
                small[i] = -1;
            }
            else
                small[i] = minimum;
        }
        int[] great = new int[n];

        great[n - 1] = -1;
        for (i = n - 2; i >= 0; i--)
        {
            if (arr[i] >= arr[maximum])
            {
                maximum = i;
                great[i] = -1;
            }
            else
                great[i] = maximum;
        }
        for (i = 0; i < n; i++)
        {
            if (small[i] != -1 && great[i] != -1)
            {
                System.out.println(arr[small[i]] + " " + arr[i] + " " + arr[great[i]]);
                return;
            }
        }
        System.out.println("3 numbers not found");
        return;
    }
    public static void main(String[] args)
    {
        int arr[] = { 11,34,2,5,1,7,4 };
        getTriplet(arr);
    }
}
2 5 7

複雜度分析

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 我們遍歷了所有的數組元素。 並且因為數組的大小為N。時間複雜度也是線性的。

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 我們一直在為每個數組元素存儲較小和較大的元素。 因此,空間複雜度也是線性的。