当前位置：首页 > news >正文

[特殊字符] 数组中的递增三元组：O(n) 时间高效查找，面试必考！

news 2026/5/8 6:38:28

给定一个整数数组arr[]，长度为 n，我们需要找出三个元素a[i] < a[j] < a[k]且下标i < j < k。要求时间复杂度为 O(n)。如果存在多个这样的三元组，输出任意一个即可。

示例：

输入：arr[] = [12, 11, 10, 5, 6, 2, 30]，输出：5, 6, 30（因为 5 < 6 < 30，且在数组中保持顺序）
输入：arr[] = [1, 2, 3, 4]，输出：1, 2, 3
输入：arr[] = [4, 3, 2, 1]，输出：No such triplet exists

朴素方法 - O(n) 时间，O(n) 空间

核心思想：找到一个元素，它在数组左边有比它小的元素，右边有比它大的元素。

创建辅助数组smaller[0..n-1]，smaller[i]存储左侧比arr[i]小的元素的索引，如果没有则为 -1。
创建辅助数组greater[0..n-1]，greater[i]存储右侧比arr[i]大的元素的索引，如果没有则为 -1。
最后遍历smaller[]和greater[]，找到索引i使得smaller[i] != -1且greater[i] != -1。

C++ 实现

#include<iostream>#include<vector>usingnamespacestd;vector<int>find3Numbers(vector<int>&arr){intn=arr.size();vector<int>smaller(n,-1);intmin=0;for(inti=1;i<n;i++){if(arr[i]<=arr[min])min=i;elsesmaller[i]=min;}vector<int>greater(n,-1);intmax=n-1;for(inti=n-2;i>=0;i--){if(arr[i]>=arr[max])max=i;elsegreater[i]=max;}for(inti=0;i<n;i++){if(smaller[i]!=-1&&greater[i]!=-1)return{arr[smaller[i]],arr[i],arr[greater[i]]};}return{};}intmain(){vector<int>arr={12,11,10,5,6,2,30};vector<int>res=find3Numbers(arr);for(intx:res)cout<<x<<" ";return0;}

Java 实现

importjava.util.*;classGfG{staticList<Integer>find3Numbers(int[]arr){intn=arr.length;int[]smaller=newint[n];Arrays.fill(smaller,-1);intmin=0;for(inti=1;i<n;i++){if(arr[i]<=arr[min])min=i;elsesmaller[i]=min;}int[]greater=newint[n];Arrays.fill(greater,-1);intmax=n-1;for(inti=n-2;i>=0;i--){if(arr[i]>=arr[max])max=i;elsegreater[i]=max;}for(inti=0;i<n;i++){if(smaller[i]!=-1&&greater[i]!=-1)returnArrays.asList(arr[smaller[i]],arr[i],arr[greater[i]]);}returnnewArrayList<>();}publicstaticvoidmain(String[]args){int[]arr={12,11,10,5,6,2,30};List<Integer>res=find3Numbers(arr);for(intx:res)System.out.print(x+" ");}}

Python 实现

deffind3Numbers(arr):n=len(arr)smaller=[-1]*n min_idx=0foriinrange(1,n):ifarr[i]<=arr[min_idx]:min_idx=ielse:smaller[i]=min_idx greater=[-1]*n max_idx=n-1foriinrange(n-2,-1,-1):ifarr[i]>=arr[max_idx]:max_idx=ielse:greater[i]=max_idxforiinrange(n):ifsmaller[i]!=-1andgreater[i]!=-1:return[arr[smaller[i]],arr[i],arr[greater[i]]]return[]arr=[12,11,10,5,6,2,30]res=find3Numbers(arr)forxinres:print(x,end=" ")

C# 实现

usingSystem;usingSystem.Collections.Generic;classGfG{staticList<int>find3Numbers(int[]arr){intn=arr.Length;int[]smaller=newint[n];for(inti=0;i<n;i++)smaller[i]=-1;intmin=0;for(inti=1;i<n;i++){if(arr[i]<=arr[min])min=i;elsesmaller[i]=min;}int[]greater=newint[n];for(inti=0;i<n;i++)greater[i]=-1;intmax=n-1;for(inti=n-2;i>=0;i--){if(arr[i]>=arr[max])max=i;elsegreater[i]=max;}for(inti=0;i<n;i++){if(smaller[i]!=-1&&greater[i]!=-1)returnnewList<int>{arr[smaller[i]],arr[i],arr[greater[i]]};}returnnewList<int>();}staticvoidMain(){int[]arr={12,11,10,5,6,2,30};List<int>res=find3Numbers(arr);foreach(intxinres)Console.Write(x+" ");}}

说到数组的递增三元组，刚刷完这道题是不是觉得O(n)的指针技巧很巧妙？但光靠脑补指针移动，很多同学面试时还是容易卡住。这里安利一个宝藏网站——图码，它提供了60多种数据结构和算法的交互式动画可视化。

你可以直接把这道题的代码贴进去，或者自定义数组数据，看指针如何一步步移动。对于正在准备408考研或数据结构期末考试的同学，它还能上传C/C++/Java/Python代码进行可视化解析，甚至7×24小时选中代码就能问AI。
想彻底吃透这类面试必考题？赶紧去图码体验一下，让抽象的逻辑动起来。
图码-数据结构与算法交互式可视化平台
访问网站：https://totuma.cn

JavaScript 实现

functionfind3Numbers(arr){constn=arr.length;constsmaller=newArray(n).fill(-1);letmin=0;for(leti=1;i<n;i++){if(arr[i]<=arr[min])min=i;elsesmaller[i]=min;}constgreater=newArray(n).fill(-1);letmax=n-1;for(leti=n-2;i>=0;i--){if(arr[i]>=arr[max])max=i;elsegreater[i]=max;}for(leti=0;i<n;i++){if(smaller[i]!==-1&&greater[i]!==-1)return[arr[smaller[i]],arr[i],arr[greater[i]]];}return[];}constarr=[12,11,10,5,6,2,30];constres=find3Numbers(arr);for(constxofres){console.log(x+" ");}

输出：5 6 30

期望方法 - O(n) 时间，O(1) 空间

思路：先找到两个元素arr[i] < arr[j]且i < j，然后在后续遍历中找arr[k] > arr[j]。我们可以在一次遍历中完成：

维护first和second，分别表示当前遇到的最小元素和次小元素（但大于first）。
同时用prevFirst记录first更新前的值，以便在找到third时正确输出。
当遇到一个元素大于second时，就找到了三元组{prevFirst, second, x}。

C++ 实现

#include<iostream>#include<vector>#include<climits>usingnamespacestd;vector<int>find3Numbers(vector<int>&arr){intn=arr.size();if(n<3)return{};intfirst=INT_MAX,second=INT_MAX,prevFirst=INT_MAX;for(inti=0;i<n;i++){intx=arr[i];if(x<=first){first=x;}elseif(x<=second){second=x;prevFirst=first;}else{return{prevFirst,second,x};}}return{};}intmain(){vector<int>arr={12,11,10,5,6,2,30};vector<int>res=find3Numbers(arr);for(intx:res)cout<<x<<" ";return0;}

Java 实现

importjava.util.*;classGfG{staticList<Integer>find3Numbers(int[]arr){intn=arr.length;if(n<3)returnnewArrayList<>();intfirst=Integer.MAX_VALUE;intsecond=Integer.MAX_VALUE;intprevFirst=Integer.MAX_VALUE;for(inti=0;i<n;i++){intx=arr[i];if(x<=first){first=x;}elseif(x<=second){second=x;prevFirst=first;}else{returnArrays.asList(prevFirst,second,x);}}returnnewArrayList<>();}publicstaticvoidmain(String[]args){int[]arr={12,11,10,5,6,2,30};List<Integer>res=find3Numbers(arr);for(intx:res)System.out.print(x+" ");}}

Python 实现

deffind3Numbers(arr):n=len(arr)ifn<3:return[]first=float('inf')second=float('inf')prevFirst=float('inf')forxinarr:ifx<=first:first=xelifx<=second:second=x prevFirst=firstelse:return[prevFirst,second,x]return[]arr=[12,11,10,5,6,2,30]res=find3Numbers(arr)forxinres:print(x,end=" ")

C# 实现

usingSystem;usingSystem.Collections.Generic;classGfG{staticList<int>find3Numbers(int[]arr){intn=arr.Length;if(n<3)returnnewList<int>();intfirst=int.MaxValue;intsecond=int.MaxValue;intprevFirst=int.MaxValue;for(inti=0;i<n;i++){intx=arr[i];if(x<=first){first=x;}elseif(x<=second){second=x;prevFirst=first;}else{returnnewList<int>{prevFirst,second,x};}}returnnewList<int>();}staticvoidMain(){int[]arr={12,11,10,5,6,2,30};List<int>res=find3Numbers(arr);foreach(intxinres)Console.Write(x+" ");}}

JavaScript 实现

functionfind3Numbers(arr){constn=arr.length;if(n<3)return[];letfirst=Number.MAX_VALUE;letsecond=Number.MAX_VALUE;letprevFirst=Number.MAX_VALUE;for(leti=0;i<n;i++){letx=arr[i];if(x<=first){first=x;}elseif(x<=second){second=x;prevFirst=first;}else{return[prevFirst,second,x];}}return[];}constarr=[12,11,10,5,6,2,30];constres=find3Numbers(arr);console.log(res.join(" "));