I*********7
发帖数: 125 | 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***i
发帖数: 1309 | 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*****u
发帖数: 648 | 3 搞两个vector >
第一个从右往左扫存所有比当前index大值也大的index
第二个从左往右扫存所有比当前index小值也小的index
然后两两组合。 最坏情况 O(n^2)
缺点是不知道怎么去重
btw,看楼主的头像是用vi的达人啊 :)
UPDATE: 想到一个去重的办法，假设有 A[i]=A[j] i | c********t
发帖数: 5706 | 4 second this, dp也可以，一样时间复杂度。用hashset 去重
【在 b*****u 的大作中提到】
: 搞两个vector >
: 第一个从右往左扫存所有比当前index大值也大的index
: 第二个从左往右扫存所有比当前index小值也小的index
: 然后两两组合。 最坏情况 O(n^2)
: 缺点是不知道怎么去重
: btw,看楼主的头像是用vi的达人啊 :)
: UPDATE: 想到一个去重的办法，假设有 A[i]=A[j] i
| I*********7
发帖数: 125 | 5 啊。。。谢谢。。。没想到是这个方法。。。一直在纠结是不是和最大递增子序列有关
系。。想了好久没想到用这么直观的方法就做好了！
【在 b*****u 的大作中提到】
: 搞两个vector >
: 第一个从右往左扫存所有比当前index大值也大的index
: 第二个从左往右扫存所有比当前index小值也小的index
: 然后两两组合。 最坏情况 O(n^2)
: 缺点是不知道怎么去重
: btw,看楼主的头像是用vi的达人啊 :)
: UPDATE: 想到一个去重的办法，假设有 A[i]=A[j] i
| I*********7
发帖数: 125 | 6 大牛。请问dp做法的具体步骤是怎样的呢。。。
【在 c********t 的大作中提到】
: second this, dp也可以，一样时间复杂度。用hashset 去重
| I*********7
发帖数: 125 | 7 这题用线段树好像可以提高效率。线段树写起来太烦啊。。
【在 l***i 的大作中提到】
: interviewstreet or hackerrank.com
: Some people are suggesting segment tree or similar structure.
| c********t
发帖数: 5706 | 8 我说错了，ls的方法就是dp
【在 I*********7 的大作中提到】
: 大牛。请问dp做法的具体步骤是怎样的呢。。。
| I*********7
发帖数: 125 | 9 大牛，求具体思路。。感激不尽。这个方法貌似很高端
【在 c********t 的大作中提到】
: 我说错了，ls的方法就是dp
| c********t
发帖数: 5706 | 10 俺不是大牛啊！
哈哈，时间复杂度变O(n^2)了，虽然空间是O(1),所以抛弃了。如果是找出任意一组，
可以用。
【在 I*********7 的大作中提到】
: 大牛，求具体思路。。感激不尽。这个方法貌似很高端
| I*********7
发帖数: 125 | 11 STL有给vector去重的办法，关键是O(n^2)的方法只能过前几个测试。后面的全部TLE了
。。。
【在 b*****u 的大作中提到】
: 搞两个vector >
: 第一个从右往左扫存所有比当前index大值也大的index
: 第二个从左往右扫存所有比当前index小值也小的index
: 然后两两组合。 最坏情况 O(n^2)
: 缺点是不知道怎么去重
: btw,看楼主的头像是用vi的达人啊 :)
: UPDATE: 想到一个去重的办法，假设有 A[i]=A[j] i
| b*****u
发帖数: 648 | 12 是不是还可以优化一下，比如往右扫，遇见比自己大的就不需要扫下去了，直接是它的
子集。左边也是，遇见小于等于自己的就从比它小的左侧数里挑
【在 I*********7 的大作中提到】
: STL有给vector去重的办法，关键是O(n^2)的方法只能过前几个测试。后面的全部TLE了
: 。。。
| i******t
发帖数: 52 | 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，可以不用排序 |
|
