在线性时间内找到大小为3的排序子序列


难度级别 中等
经常问 Avalara Capital One公司 堡垒 思杰 易趣 晶圆厂 新思
排列

问题陈述

问题“在线性时间内找到大小为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” 是数组中元素的数量。 我们一直在为每个数组元素存储较小和较大的元素。 因此,空间复杂度也是线性的。