interviewstreet三重挑战 [英] interviewstreet Triplet challenge
问题描述
有一个整数阵列D，它不包含相同的值的两个以上的元素。有多少不同的上升三倍（D [1] - ; D [J]＆LT; D [K]，I＆LT; J＆LT; K）是present？
There is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples (d[i] < d[j] < d[k], i < j < k) are present?
输入格式：
的第一行包含一个正整数N表示数组中元素的数目。其次是含有N个整数，没有领先相隔一个空格/后间隔一行
The first line contains an integer N denoting the number of elements in the array. This is followed by a single line containing N integers separated by a single space with no leading/trailing spaces
输出格式为：
有一个单一的整数，表示不同的递增数量的三倍present阵列中的
A single integer that denotes the number of distinct ascending triples present in the array
约束：
N'LT = 10 ^ 5 数组中的每个值是present最多两次 数组中的每一个值是一个32位的正整数
N <= 10^5 Every value in the array is present at most twice Every value in the array is a 32-bit positive integer
样品输入：
6
1 1 2 2 3 4
示例输出：
4
说明：
在不同的三元组
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
另一个测试案例：
Another test case:
输入：
10
1 1 5 4 3 6 6 5 9 10
输出：
28
我试着使用DP来解决。但是，在15个测试案例仅7测试用例通过。 请帮助解决这个问题。
I tried to solve using DP. But out of 15 test cases only 7 test cases passed. Please help solve this problem.
推荐答案
您应该注意的是，你只需要知道这是不是一个特定的元素知道有多少三元它作为中间点小/大元素的数量对于。使用这个你可以计算出三倍的数量很容易，唯一剩下的问题就是要摆脱重复的，但考虑到您被限制为最多2相同的元素，这是微不足道的。
You should note that you only need to know the number of elements that are smaller/larger than a particular element to know how many triples it serves as the middle point for. Using this you can calculate the number of triples quite easily, the only remaining problem is to get rid of duplicates, but given that you are limited to at most 2 of the same element, this is trivial.
我解决了使用二进制索引树的http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees.
I solved using a Binary Index Tree http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees.
我还做了一个小的写了起来， http://www.kesannmcclean.com/?p= 223 。
I also did a small write up, http://www.kesannmcclean.com/?p=223.
这篇关于interviewstreet三重挑战的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
