问一道某网站上看到的题目，求递增的三元组 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道某网站上看到的题目，求递增的三元组

问一道某网站上看到的题目，求递增的三元组# JobHunting - 待字闺中

I*72013-02-22 08:02

1 楼

给定一个数组，里面所有的元素在数组中最多出现两次，要求求出所有的不同的三元组
的个数，三元组要满足 arr[i] < arr[j] < arr[k] 并且 i < j < k
例子：{ 1,1,2,2,3,4 } 结果：4
因为有{ 1,2,3 },{ 1,2,4 },{ 1,3,4 },{ 2,3,4 }
本人太菜了，这题想了好久也没想出来。。求各位大神解答

l*i2013-02-22 08:02

2 楼

interviewstreet or hackerrank.com
Some people are suggesting segment tree or similar structure.

【在 I*********7 的大作中提到】

: 给定一个数组，里面所有的元素在数组中最多出现两次，要求求出所有的不同的三元组
: 的个数，三元组要满足 arr[i] < arr[j] < arr[k] 并且 i < j < k
: 例子：{ 1,1,2,2,3,4 } 结果：4
: 因为有{ 1,2,3 },{ 1,2,4 },{ 1,3,4 },{ 2,3,4 }
: 本人太菜了，这题想了好久也没想出来。。求各位大神解答

b*u2013-02-22 08:02

3 楼

搞两个vector >
第一个从右往左扫存所有比当前index大值也大的index
第二个从左往右扫存所有比当前index小值也小的index
然后两两组合。最坏情况 O(n^2)
缺点是不知道怎么去重
btw,看楼主的头像是用vi的达人啊 :)
UPDATE: 想到一个去重的办法，假设有 A[i]=A[j] i

c*t2013-02-22 08:02

4 楼

second this, dp也可以，一样时间复杂度。用hashset 去重

【在 b*****u 的大作中提到】

: 搞两个vector >
: 第一个从右往左扫存所有比当前index大值也大的index
: 第二个从左往右扫存所有比当前index小值也小的index
: 然后两两组合。最坏情况 O(n^2)
: 缺点是不知道怎么去重
: btw,看楼主的头像是用vi的达人啊 :)
: UPDATE: 想到一个去重的办法，假设有 A[i]=A[j] i

I*72013-02-22 08:02

5 楼

啊。。。谢谢。。。没想到是这个方法。。。一直在纠结是不是和最大递增子序列有关
系。。想了好久没想到用这么直观的方法就做好了！

【在 b*****u 的大作中提到】

I*72013-02-22 08:02

6 楼

大牛。请问dp做法的具体步骤是怎样的呢。。。

【在 c********t 的大作中提到】

: second this, dp也可以，一样时间复杂度。用hashset 去重

I*72013-02-22 08:02

7 楼

这题用线段树好像可以提高效率。线段树写起来太烦啊。。

【在 l***i 的大作中提到】

: interviewstreet or hackerrank.com
: Some people are suggesting segment tree or similar structure.

c*t2013-02-22 08:02

8 楼

我说错了，ls的方法就是dp

【在 I*********7 的大作中提到】

: 大牛。请问dp做法的具体步骤是怎样的呢。。。

I*72013-02-22 08:02

9 楼

大牛，求具体思路。。感激不尽。这个方法貌似很高端

【在 c********t 的大作中提到】

: 我说错了，ls的方法就是dp

c*t2013-02-22 08:02

10 楼

俺不是大牛啊！
哈哈，时间复杂度变O(n^2)了，虽然空间是O(1),所以抛弃了。如果是找出任意一组，
可以用。

【在 I*********7 的大作中提到】

: 大牛，求具体思路。。感激不尽。这个方法貌似很高端

I*72013-02-22 08:02

11 楼

STL有给vector去重的办法，关键是O(n^2)的方法只能过前几个测试。后面的全部TLE了
。。。

【在 b*****u 的大作中提到】

b*u2013-02-22 08:02

12 楼

是不是还可以优化一下，比如往右扫，遇见比自己大的就不需要扫下去了，直接是它的
子集。左边也是，遇见小于等于自己的就从比它小的左侧数里挑

【在 I*********7 的大作中提到】

: STL有给vector去重的办法，关键是O(n^2)的方法只能过前几个测试。后面的全部TLE了
: 。。。

i*t2013-02-22 08:02

13 楼

看看这个对不对：
因为 arr[i] < arr[j] < arr[k]，所以只考虑不重复的。扫一边，找到unique的元
素数m,排序
f2(i)表示在unique元素array从1到i，有多少个valid的pair， i(i-1)/2
f3(i)表示从1到i，有多少个valid的3-tuple， f3(i)=f2(i-1)+f3(i-1)
f3(i)-f3(i-1)=(i-1)(i-2)/2
最后算出f3(m),其实这个地推公式有形式解，如果不要输出所有tuple，可以不用排序