最長遞增子序列的構造(N log N)


難度級別
經常問 亞馬遜 銀行集市 Paytm Samsung
排列 二元搜尋 動態編程

問題陳述

給你一個 排列 of 整數。 問題“最長增長子序列的構造(N log N)”要求構造最長增長子序列。

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

解釋

我們找出在數組中增加的最長子序列。

最長遞增子序列的構造(N log N)

最長遞增子序列(N log N)的構造算法

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

解釋

我們給出了一個整數數組,並要求構造 最長的遞增子序列。 為此,我們將使用兩個數組lastIndexes和firstIndexes並將其分別填充為0和-1的值。 firstIndexes數組將初始化為1。因為這會將值存儲為位置作為索引。 我們將在遍歷數組時更新值。

我們將遍歷數組從1到n。 其中n是數組的長度。 在遍歷時,數組lastIndexes將用作數組的位置或索引。 我們將檢查一些條件,我們將檢查當前數組元素是否小於lastIndexes [leng-1]的數組。 Length最初定義為1,這意味著至少我們將擁有長度為1的子序列。因此,如果上述條件為true,則將lastIndexes [0]更新為1。

我們需要檢查arr [i]是否大於lastIndexes [n-1]的數組。 然後更新兩個數組,將firstIndexes [i]設置為lastIndexes [n-1]的最後一個值,將lastIndexes [leng]設置為i,並增加leng值。 否則,我們必須找出當前數組元素的位置。 為此,我們將使用二進制搜索並將該索引獲取到該位置。 並將lastIndexes [position-1]的值更新為firstIndexes [i],將lastIndexes [position]的值更新為i。

遍歷後,我們需要打印數組。 為此,我們將從最後一個遍歷到0th 每次遍歷後定位並初始化每個索引為firstIndexes [i],並打印數組的每個可能值。

推薦碼

構造最長遞增子序列的C ++代碼(N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

構造最長遞增子序列的Java代碼(N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

複雜度分析

時間複雜度

O(n log n) 其中“ n”是數組中元素的數量。 由於我們使用了二分查找法,該算法為我們提供了一個對數因子。 但是,如果我們不得不為每個索引調用二進制搜索。 然後,在最壞的情況下,時間複雜度將為O(N log N)。

空間複雜度

O(N) 其中“ n”是數組中元素的數量。 由於我們創建了兩個臨時數組firstIndexes和lastIndexes。 空間複雜度變為 上).