10

我们得到一个数字数组，我们想找到一个按升序排序的大小为 4 的子序列。

for eg ARRAY                :  -4 2 8 3 1 5
sorted subsequence of size 4 : -4 2 3 5

PS：有一种方法可以找到大小为 3 的排序子序列（请参阅此）。我试图沿着同样的思路思考，但似乎无法找到 4 个整数的解决方案。

4

5 回答 5

19

这是一个解决方案，它将通过对输入k+1进行传递来找到固定大小的排序子序列。k每遍都是从左到右完成的。

Pass 1：创建一个辅助数组p1[0..n-1]。应该存储小于并且位于（换句话说：和）左侧的数字p1[i]的索引。如果没有这样的元素，则应该包含 -1。（与大小为 3 的解决方案中的数组相同）。jarr[i]arr[i]j<iarr[j]<arr[i]p1[i]p1smaller

Pass 2：创建一个辅助数组p2[0..n-1]。应存储小于、位于 、 左侧的数字p2[i]的索引，并且满足（换句话说：、和）。如果没有这样的元素，则应该包含 -1。jarr[i]arr[i]p1[j] != -1j<iarr[j]<arr[i]p1[j]!=-1p2[i]

……

Pass k：创建一个辅助数组pk[0..n-1]。应存储小于、位于 、 左侧的数字pk[i]的索引，并且满足（换句话说：、和）。如果没有这样的元素，则应该包含 -1。jarr[i]arr[i]p(k-1)[j] != -1j<iarr[j]<arr[i]p(k-1)[j]!=-1pk[i]

在第kth 遍之后，每个元素pk[i] != -1对应于 size 的排序子序列中的最大元素k+1。

k第一遍的伪代码（k>1）：

function do_kth_pass(pk[], p_k_minus_1[])
    min = -1
    for i in 0..n-1:
        if min != -1 and arr[i] > arr[min]:
            pk[i] = min
        else
            pk[i] = -1
        if p_k_minus_1[i] != -1 and (min == -1 or arr[i] < arr[min]):
            min = i

例子：

Index:   0  1  2  3  4  5
Array:  -4  2  8  3  1  5
p1:     -1  0  0  0  0  0
p2:     -1 -1  1  1 -1  4
p3:     -1 -1 -1 -1 -1  3

经过 3 次通过后，您有 p3[5] != -1，因此存在大小为 4 的排序子序列。其元素的索引是：p1[p2[p3[5]]], p2[p3[5]], p3[5], 5即 0,1,3,5

于 2013-07-15T13:43:57.093 回答
4

拥有更大或更小的数组是一个不错的选择，但它会增加空间复杂度。下面，是一种在没有额外数组空间的情况下在线性子序列中查找四个数字的解决方案，而是使用恒定空间并且只遍历数组一次。

#include <iostream>

void sortedSubseqFour(int a[], int n)
{
    int small = INT_MAX;
    int middle_1 = INT_MAX;
    int middle_2 = INT_MAX; 
    int greater = 0;

    int main_small = 0;
    int main_middle_1 = 0;

    int main_main_small = 0;

    for(int i = 0; i<n; i++)
    {
        if (a[i] <= small)
            small = a[i];
        else if (a[i] <= middle_1)
        {
            middle_1 = a[i];
            main_small = small;
        }
        else if (a[i] <= middle_2)
        {
            middle_2 = a[i];
            main_middle_1 = middle_1;
            main_main_small = main_small;
        }
        else
        {
            greater = a[i];
            break;
        }
    }
    //end of loop

    if (greater != 0)
        std::cout << main_main_small << '\t' << main_middle_1 << '\t'
                  << middle_2 << '\t' << greater;
    else
        std::cout << "No such Quadruple";
}

int main()
{
    int arr[10] = {6, 7, 5, 1, 4, 3, 0, 7, 2, 11};
    int n = 10; 

    sortedSubseqFour(arr, n);
    return 0;
}

上述方法在设置当前最小值时会记住所有最小值。通过删除和部分代码，相同的代码也可用于3数组中大小的排序子序列。main_main_smallmiddle_2

如果要将相同的代码扩展到 size k，那么在说 minimum i，我们必须记住所有 minimum 的 before i，即min_1, min_2,... until min_i。只有在最后一个最小值，即我们的子序列中的最大值，我们才打破，不需要记住之前或当前的最小值。

如果发现任何错误，请告知！

于 2017-05-25T11:25:04.357 回答
1

您可以找到最长的递增子序列，并查看它的大小是否大于等于 4（或者甚至 k，以防您需要为更一般的问题找到它）。如果最长递增子序列的长度小于 4（或 k），您可以报告不存在这样的子序列。LIS 可以在O(nlog(n))

于 2017-11-24T18:47:59.170 回答
0

创建一个smaller和greater数组，类似于对大小为 3 的子序列所做的操作。除此之外，还有一个betweenSmallerAndCurrent数组，用于存储介于最小值和当前元素之间的值的索引 - 无论是在值中还是在索引中。更明确地说：

betweenSmallerAndCurrent[i] = -1 or

input[smaller[i]] < input[betweenSmallerAndCurrent[i]] < input[value[i]] and
smaller[i] < betweenSmallerAndCurrent[i] < value[i]

构建它应该很容易。

您只需返回索引iwhere betweenSmallerAndCurrent[i]，smaller[betweenSmallerAndCurrent[i]]并且greater[i]都已初始化。请注意，我们不能简单地检查smaller[i]，因为我们可能有类似的东西[2,3,1,4,5]，在这种情况下，当我们到达 时4，第二个最小值3在当前最小值之前1。

例子：

Indices: 0  1  2  3  4  5  6  7
Input:   12 11 10 5  6  2  9  30

smaller: -1 -1 -1 -1 3  -1 5  5
betweenSmallerAndCurrent: 
         -1 -1 -1 -1 -1 -1 4  4

greater: 7  7  7  7  7  7  7  -1

初始化所有值的唯一索引是 6（输入值 9）。

Java 代码：（未经过广泛测试）

void find4Numbers(int arr[], int n)
{
   int max = n-1; //Index of maximum element from right side
   int min = 0, second = -1; //Index of minimum element from left side
   int i;

   // Create an array that will store index of a smaller
   // element on left side. If there is no smaller element
   // on left side, then smaller[i] will be -1.
   int[] smaller = new int[n];
   int[] betweenSmallerAndCurrent = new int[n];
   smaller[0] = -1;  // first entry will always be -1
   betweenSmallerAndCurrent[0] = -1;
   for (i = 1; i < n; i++)
   {
       if (arr[i] <= arr[min])
       {
          min = i;
          smaller[i] = -1;
          betweenSmallerAndCurrent[i] = -1;
       }
       else
       {
          smaller[i] = min;
          if (second != -1 && arr[second] < arr[i])
             betweenSmallerAndCurrent[i] = second;
          else 
             betweenSmallerAndCurrent[i] = -1;
          if (second == -1 || arr[i] < arr[second])
             second = i;
       }
   }

   // Create another array that will store index of a
   // greater element on right side. If there is no greater
   // element on right side, then greater[i] will be -1.
   int[] greater = new int[n];
   greater[n-1] = -1;  // last entry will always be -1
   for (i = n-2; i >= 0; i--)
   {
       if (arr[i] >= arr[max])
       {
          max = i;
          greater[i] = -1;
       }
       else
          greater[i] = max;
   }

   // Make sure they're right
   System.out.println(Arrays.toString(smaller));
   System.out.println(Arrays.toString(betweenSmallerAndCurrent));
   System.out.println(Arrays.toString(greater));

   // Now find a number which has both a greater number on
   // right side and smaller number on left side
   for (i = 0; i < n; i++)
   {
       if (betweenSmallerAndCurrent[i] != -1 && smaller[betweenSmallerAndCurrent[i]] != -1 && greater[i] != -1)
       {
          System.out.printf("%d %d %d %d\n",
                            arr[smaller[betweenSmallerAndCurrent[i]]],
                            arr[betweenSmallerAndCurrent[i]],
                            arr[i],
                            arr[greater[i]]);
          return;
       }
   }

   // If we reach number, then there are no such 3 numbers
   System.out.println("No such triplet found");
}

您可能会注意到，除了 C 到 Java 的转换和添加的初始化之外，主要代码的变化在于设置的循环中smaller。代码应该很容易理解 - 如果遇到问题，请尝试将其翻译成文字。

测试。

于 2013-07-15T14:00:32.277 回答
0

对于每个元素，找到下一个更大的元素索引 else -1 现在将其视为一个图并找到长度为 k 的路径（如果存在）这可以使用哈希表和记忆化在线性时间内轻松完成。

于 2018-03-04T15:12:41.560 回答