logo标签列表

如何在线性时间内找到一个数组中按递增顺序排列且索引也递增的三个数字

arrayscalgorithmtime-complexity
22

我在一个网站上遇到了这个问题。如该网站所述，这是亚马逊面试时提出的问题。在给定的限制条件下，我无法找出合适的解决方案。

给定一个由n个整数组成的数组，请在O(n)时间内找到3个元素，使得a[i] < a[j] < a[k]且i < j < k。

3
你尝试了什么？ - H H
@HenkHolterman 我的思路带我走向了与 twall 下面的方法类似的方向。但最后我发现了自己解决方案中的错误... :( - rajneesh2k10
14个回答
33

以下是如何解决该问题的方法。您需要对数组进行三次迭代。在第一次迭代中，标记所有右侧有大于它们的元素的值，在第二次迭代中，标记所有左侧有小于它们的元素的元素。现在您的答案将是具有两者的元素：

int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));

int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
   if (greatest_value_so_far > a[i]) {
     greater_on_right[i] = greatest_index;
   } else {
     greatest_value_so_far = a[i];
     greatest_index = i;
   }
}

// Do the same on the left with smaller values


for (int i =0;i<n;++i) {
  if (greater_on_right[i] != -1 && smaller_on_left[i] != -1) {
    cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_right[i] << endl;
  }
}

这种解决方案在整个数组上迭代了3次，因此是线性的。我没有提供完整的解决方案，这样您就可以在左侧进行训练，看看是否理解我的想法。很抱歉我无法给出提示而不显示实际解决方案。

希望这解决了你的问题。

1
很棒的想法！我做事情的方式有太多缺陷了，我承认，我应该从更广泛的角度去思考：线性并不意味着在一个迭代中完成，尽管我相当确定这是可行的。我稍后会尝试找到解决方案！ - devsnd
1
请纠正我，如果输入是{1,2,3,4}，那么你并没有找到所有的三元组，它们是[1,2,3][1,2,4][1,3,4][2,3,4]。 - rops
1
@daniele，你只需要找到一个三元组，而不是所有的三元组。你不能指望能够在线性时间内打印所有三元组，因为它们的数量可能是立方级别的。 - Ivaylo Strandjev
@IvayloStrandjev 这个逻辑存在处理局部最大值问题。对于数组8,9,7,10,2,3,11，greater_on_right只指向不正确的最后一个元素。对于这个输入，它理想情况下应该打印输出8,9,10而不是8,9,11。以下是你代码片段的输出： 索引:0，1，6 列表:8，9，11 索引:2，3，6 列表:7，10，11 索引:4，5，6 列表:2，3，11。 - Vivek
1
@Vivek 请再仔细阅读问题。OP要求算法找到一个三元组，而不是所有的三元组。顺便说一下，我的代码可以很容易地适应找到最左边的那个。 - Ivaylo Strandjev
显示剩余4条评论
3
一次遍历线性时间，只需O(1)的额外空间（4个变量）。非常高效（每次迭代只有几个比较/分支，数据移动也不多）。 这不是我的原创想法或算法，我只是整理和注释了ideone fork中的代码。您可以在那里添加新的测试用例并在线运行它。原始代码由Kenneth在www.geeksforgeeks.org的评论中发布。这是一个很棒的算法，但原始实现在实际循环之外有一些非常愚蠢的代码。（例如，使用类的两个成员变量而不是局部变量，并将函数实现为class Solution的成员函数...变量名也很糟糕。我选择了相当冗长的变量名。）
如果你想把你的代码发表为答案，肯定没问题。我不是在试图窃取算法的功劳。（尽管我确实花了一些时间来撰写这篇解释，并思考它的工作原理。）
上面的讨论线程中的主要文章与Ivaylo Strandjev的答案相同。（主文章的代码是Pramod在几个月后作为对这个问题的答案发布的。这就是我在那里的评论中找到有趣答案的方式。）
由于您只需要找到一个解决方案，而不是所有解决方案，因此没有像您预期的那样多的特殊情况。如果选择正确的状态保留，实际上不需要跟踪您看到的每个可能的起始和中间值，甚至不需要回溯。
主要技巧包括：

  • 在单调递减值序列中，仅需考虑最后一个值。这适用于第一个（较小的）和第二个（中间的）候选元素。

  • 每当你看到一个较小的中间元素候选时，你可以重新开始寻找最终元素或更好的中间候选元素。如果您尚未在当前中间候选项之前找到一系列3个递增元素，则min-so-far和新的较小中间候选项与您已经检查过的数字一样好（宽容度高，灵活性）。 （有关更好的措辞，请参见代码中的注释。）

    其他一些答案犯了这个错误：每次看到新的最小或最大元素而不是中间元素时都要重新开始。 您跟踪当前已见到的最小值，但直到您看到一个新的中间值才会做出反应或利用它。

为了查找新的中间候选元素，您需要检查它们是否小于当前的中间候选元素，并且 != 迄今为止看到的最小元素。

我不确定这个想法是否可以扩展到4个或更多个连续值。查找新的第三个元素候选项可能需要单独跟踪当前候选第二个和第三个元素之间的最小值，这可能会变得棘手，并且需要更多的条件语句。 但是，如果可以通过恒定大小的状态和一次无回溯的传递正确地执行，则仍将是线性时间。

// Original had this great algorithm, but a clumsy and weird implementation (esp. the code outside the loop itself)

#include <iostream>
#include <vector>

using namespace std;

//Find a sorted subsequence of size 3 in one pass, linear time
//returns an empty list on not-found
vector<int> find3IncreasingNumbers(int * arr, int n)
{
    int min_so_far = arr[0];
    int c_low, c_mid;            // candidates
    bool have_candidates = false;

    for(int i = 1; i < n; ++i)  {
        if(arr[i] <= min_so_far)  // less-or-equal prevents values == min from ending up as mid candidates, without a separate else if()continue;
            min_so_far = arr[i];
        else if(!have_candidates || arr[i] <= c_mid) {
            // If any sequence exists with a middle-numbers we've already seen (and that we haven't already finished)
            // then one exists involving these candidates
            c_low = min_so_far;
            c_mid = arr[i];
            have_candidates = true;
        } else {
            // have candidates and arr[i] > c_mid
            return vector<int> ( { c_low, c_mid, arr[i] } );
        }
    }

    return vector<int>();  // not-found
}

int main()
{
    int array_num = 1;

// The code in this macro was in the original I forked.  I just put it in a macro.  Starting from scratch, I might make it a function.
#define TRYFIND(...) do { \
        int arr[] = __VA_ARGS__ ; \
        vector<int> resultTriple = find3IncreasingNumbers(arr, sizeof(arr)/sizeof(arr[0])); \
        if(resultTriple.size()) \
            cout<<"Result of arr" << array_num << ": " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl; \
        else \
            cout << "Did not find increasing triple in arr" << array_num << "." <<endl; \
        array_num++; \
    }while(0)

    TRYFIND( {12, 11, 10, 5, 6, 2, 30} );
    TRYFIND( {1, 2, 3, 4} );
    TRYFIND( {4, 3, 1, 2} );
    TRYFIND( {12, 1, 11, 10, 5, 4, 3} );
    TRYFIND( {12, 1, 11, 10, 5, 4, 7} );
    TRYFIND( {12, 11, 10, 5, 2, 4, 1, 3} );
    TRYFIND( {12, 11, 10, 5, 2, 4, 1, 6} );
    TRYFIND( {5,13,6,10,3,7,2} );
    TRYFIND( {1, 5, 1, 5, 2, 2, 5} );
    TRYFIND( {1, 5, 1, 5, 2, 1, 5} );
    TRYFIND( {2, 3, 1, 4} );
    TRYFIND( {3, 1, 2, 4} );
    TRYFIND( {2, 4} );

    return 0;
}

制作一个可以接受初始化列表作为参数的CPP宏很丑陋：
是否可能将大括号包含的初始化器作为宏参数传递？

尽管如此，能够轻松添加新的测试用例而不用在4个位置上编辑arr4到arr5是非常值得的。
1

只是为了好玩：
在JAVA中：

List<Integer> OrderedNumbers(int[] nums){
    List<Integer> res = new LinkedList<>();
    int n = nums.length;
    //if less then 3 elements, return the empty list
    if(n<3) return res;

    //run 1 forloop to determine local min and local max for each index
    int[] lMin = new int[n], lMax = new int[n];
    lMin[0] = nums[0]; lMax[n-1] = nums[n-1];
    for(int i=1; i<n-1; i++){
        lMin[i] = Math.min(lMin[i-1], nums[i]);
        lMax[n-i-1] = Math.max(lMax[n-i],nums[n-i-1]);
    }

    //if a condition is met where min(which always comes before nums[i] and max) < nums[i] < max, add to result set and return;
    for(int i=1; i<n-1; i++){
        if(lMin[i]<nums[i] && nums[i]<lMax[i]){
            res.add(lMin[i]);
            res.add(nums[i]);
            res.add(lMax[i]);
            return res;
        }
    }
    return res;
}
1
这个问题与计算最长递增子序列非常相似，但约束条件是该子序列的大小必须为三。最长递增子序列问题（具有O(nlog(n))解决方案）可以轻松修改为此特定问题。此解决方案具有O(n)的单次遍历复杂度和O(1)的空间复杂度。
此解决方案要求列表中仅出现唯一元素。我们使用一个在线解决方案。当我们遇到任何新元素时，它有可能扩展当前最优子序列或开始一个新的子序列。在这种情况下，由于递增子序列的最大长度为三，当前正在处理的任何新元素都可以将大小为2的序列扩展为3和1到2。因此，我们维护包含最优元素的活动列表。
在这个问题中，我们需要维护的最大活动列表数为2-一个大小为2，另一个大小为1。一旦我们遇到一个大小为3的列表，我们就有了答案。我们确保每个活动列表以最小数量终止。有关该想法的更详细说明，请参见this。
在在线解决方案的任何时候，这两个活动列表将存储列表的最有效值-列表的末尾将是可以放置在那里的最小元素。假设这两个列表如下：
大小为2的列表=>[a,b]
大小为1的列表=>[c]
可以轻松编写初始列表（请参见下面的代码）。假设要输入的下一个数字是d，则情况（按执行级联）如下所示：
情况1：d > b。 在这种情况下，我们已经得到了答案，因为a < b < d。

情况2: b > d > a。在这种情况下，大小为2的列表可以通过将末尾设为d来进行最优表示，而不是b，因为出现在d之后的每个元素大于b也将大于d。因此，我们用d替换b。

情况3: d < c。由于情况1和2失败了，它自动意味着d < a。在这种情况下，它可以从大小为一开始新的列表。比较大小为一的列表以获得最有效的活动列表。如果这种情况成立，我们用d替换c。

情况4: 否则。这种情况意味着d < b且c < d。在这种情况下，大小为2的列表效率低下。因此，我们用[c，d]替换[a，b]。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int two_size_first;
    int two_size_mid;
    int one_size;
    int end_index;
    vector<int> arr;

    Solution(int size) {
        end_index = two_size_mid = two_size_first = one_size = -1;
        int temp;
        for(int i=0; i<size; i++) {
            cin >> temp;
            arr.push_back(temp);
        }   
    }

    void solve() {
        if (arr.size() < 3)
            return;

        one_size = two_size_first = arr[0];
        two_size_mid = INT_MAX;

        for(int i=1; i<arr.size(); i++) {
            if(arr[i] > two_size_mid) {
                end_index = i;
                return;
            }
            else if (two_size_first < arr[i] && arr[i] < two_size_mid) {
                two_size_mid = arr[i];
            }
            else if (one_size > arr[i]) {
                one_size = arr[i];
            }
            else {
                two_size_first = one_size;
                two_size_mid = arr[i];
            }
        }
    }

    void result() {
        if (end_index != -1) {
            cout << two_size_first << " " << two_size_mid << " " << arr[end_index] << endl; 
        }
        else {
            cout << "No such sequence found" << endl;
        }
    }
};

int main(int argc, char const *argv[])
{
    int size;
    cout << "Enter size" << endl;
    cin >> size;
    cout << "Enter "  << size << " array elements" << endl;
    Solution solution(size);

    solution.solve();
    solution.result();
    return 0;
}
这个想法也可以用来找到长度大于3的递增子序列。 - Shivam Tripathi
1

我在这里发布了另一种解决方法链接。

#include<stdio.h>

// A function to fund a sorted subsequence of size 3
void find3Numbers(int arr[], int n)
{
   int max = n-1; //Index of maximum element from right side
   int min = 0; //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];
   smaller[0] = -1;  // first entry will always be -1
   for (i = 1; i < n; i++)
   {
       if (arr[i] < arr[min])
       {
          min = i;
          smaller[i] = -1;
       }
       else
          smaller[i] = min;
   }

   // 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;
   }

   // 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 (smaller[i] != -1 && greater[i] != -1)
       {
          printf("%d %d %d", arr[smaller[i]],
                 arr[i], arr[greater[i]]);
          return;
       }
   }

   // If we reach number, then there are no such 3 numbers
   printf("No such triplet found");
   return;
}

// Driver program to test above function
int main()
{
    int arr[] = {12, 11, 10, 5, 6, 2, 30};
    int n = sizeof(arr)/sizeof(arr[0]);
    find3Numbers(arr, n);
    return 0;
}
2
与@Ivaylo Strandjev给出的解决方案完全相同。 - Trying
那个链接是一个编程挑战网站，许多解决方案都在评论中发布。 - Peter Cordes
0
这是一个关于编程的内容，翻译如下：

这个问题有一个时间复杂度为O(n)，空间复杂度为O(1)的解决方案。

bool increasingTriplet(vector<int>& a) {

    int i,n=a.size(),first=INT_MAX,second=INT_MAX;
    if(n<3)
        return false;

    for(i=0;i<n;i++)
    {
        if(a[i]<=first)
            first = a[i];
        else if(a[i]<=second)
            second = a[i];
        else
            return true;
    }
    return false;
}

如果数组中存在一对按升序排列的三个元素，则此函数返回true。 您还可以修改此函数以打印所有3个元素或它们的索引。只需更新它们的索引以及变量first和second。

0
这是我的O(n)解决方案，具有O(1)空间复杂度：- 只需一个函数，返回由三个值（如果存在）组成的向量。
`vector<int> find3Numbers(vector<int> A, int N)
 {
    int first=INT_MAX,second=INT_MAX,third=INT_MAX,i,temp=-1;
    vector<int> ans;
    for(i=0;i<N;i++)
    {
        if(first!=INT_MAX&&second!=INT_MAX&&third!=INT_MAX)
        {
            ans.push_back(first);
            ans.push_back(second);
            ans.push_back(third);
            return ans;
        }
        if(A[i]<=first)
        {
            if(second!=INT_MAX)
            {
                if(temp==-1)
                {
                    temp=first;
                }
                first=A[i];
            }
            else
            {
                first=A[i];
            }
        }
        else if(A[i]<=second)
        {
            second=A[i];
            temp=-1;
        }
        else
        {
            if(temp!=-1)
            {
                first=temp;
            }
            third=A[i];
        }
    }
    if(first!=INT_MAX&&second!=INT_MAX&&third!=INT_MAX)
    {
        ans.push_back(first);
        ans.push_back(second);
        ans.push_back(third);
        return ans;
    }
    return ans;
}`
0

我的方法 - O(N)时间两次遍历，使用两个变量的O(1)空间

对于我们访问的数组的每个元素，我们维护其左侧可能的最小值，以检查该元素是否可能是中间元素，并记录其左侧可能的最小中间元素，以检查该元素是否可能是候选的第三个元素或者它可以与迄今为止找到的较低值的中间元素形成中间元素。将min so far和middle so far初始化为INT_MAX。

因此，对于每个元素，我们必须检查：

如果特定的数组元素大于迄今为止的中间元素的最小值，则该数组元素是答案，其中thi为第三个元素，min中间元素为中间元素（我们将不得不通过一次遍历来搜索第三个元素）

否则，如果特定的数组元素大于迄今为止的最小值，则该元素可能是候选的中间元素，现在我们必须检查候选的中间元素是否小于当前中间元素，如果是，则更新当前中间元素

否则，如果特定的数组元素小于迄今为止的最小值，则使用arr[i]更新迄今为止的最小值。

因此，对于我们访问的数组的每个元素，我们保持其左侧的最小值以检查该元素是否可能是中间元素，并记录其左侧的最小中间元素以检查该元素是否可能是候选第三个元素或者它可以与迄今为止找到的较低值的中间元素形成中间元素。
#include using namespace std;

int main()
{
int i,j,k,n;
cin >> n;
int arr[n];
for(i = 0;i < n;++i)
    cin >> arr[i];
int m = INT_MAX,sm = INT_MAX,smi;// m => minimum so far found to left
for(i = 0;i < n;++i)// sm => smallest middle element found so far to left
{
    if(arr[i]>sm){break;}// This is the answer
    else if(arr[i] < m ){m = arr[i];}
    else if(arr[i] > m){if(arr[i]<sm){sm = arr[i];smi = i;}}
    else {;}
}
if((i < n)&&(arr[i]>sm))
{
    for(j = 0;j < smi;++j){if(arr[j] < sm){cout << arr[j] << " ";break;}}
    cout << sm << " " << arr[i]<< endl;
}
else 
    cout << "Such Pairs Do Not Exist" << endl;
return 0;
}
0

我的解决方案如下。

public boolean increasingTriplet(int[] nums) {

    int min1 = Integer.MAX_VALUE;
    int min2 = Integer.MAX_VALUE;

    for (int i =0; i<nums.length; i++) {
        if (nums[i]<min1) {
            min1 = nums[i];
        } else if (nums[i]<min2 && nums[i]>min1) {
            min2=nums[i];
        } else if (nums[i]>min2) {
            return true;
        }
    }
    return false;
}
-1

抱歉，我忍不住要解决这个谜题了... 这是我的解决方案。

//array indices
int i, j, k = -1;
//values at those indices
int iv, jv, kv = 0;
for(int l=0; l<a.length(); l++){
    //if there is a value greater than the biggest value
    //shift all values from k to i
    if(a[l]>kv || j == -1 || i == -1){
        i = j;
        iv = jv;
        j = k;
        jv = kv
        kv = a[l]
        k = l
    }
    if(iv < jv && jv < kv && i < j && j < k){
        break;
    }    
}
+1。不错。:)
不过我不会用iv、jv和kv，但我猜这样更有效率，所以我不能抱怨。你怎么知道你找到了它？检查i != j && j != k。 - Neil
3
这是要做什么？对于输入的 "100、1、2、3"，你只会设置 kv = 100，而不考虑是否存在一组有效的三个数字。我需要翻译这段内容。 - Ivaylo Strandjev
我更新了我的回答，感谢 izomorphius 和 Neil 的贡献。 - devsnd
好的，现在针对输入“1001,100,200,1,2,3”，你会怎么做呢？我认为你的方法方向不正确。 - Ivaylo Strandjev
当一个高于kv值的新值不在序列中时，它会失败。在1 5 2 3上它会失败（因为移位会弃掉1而不是5）。我认为即使修复了这个bug，它仍然会错过一些东西，因为它不能回溯考虑以被忽略的值作为起始的序列，这些值小于在寻找两个其他候选数之后的第三个递增值时所拥有的kv。（所以这个想法是基本有缺陷的，不幸的是。） - Peter Cordes
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接