-2

大家好,我在 InterviewSteet 网站上发现了有趣的问题。我对这个问题有点困惑。请帮助我理解问题。我得到了 35 个三元组,但样本中预计只有 28 个。我添加了我的 35triples 输出。请帮我找到 28 个三元组。wat是我理解问题的错误。一世

问题:

有一个整数数组 d,它不包含两个以上相同值的元素。存在多少个不同的升序三元组 (d[i] < d[j] < d[k], i < j < k)?

输入格式

第一行包含一个整数 N,表示数组中元素的数量。接下来是包含 N 个整数的单行,由一个空格分隔,没有前导/尾随空格

输出格式:

一个整数,表示数组中存在的不同升三元组的数量

约束:

N <= 10^5
Every element of the array is present at most twice
Every element of 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)

我的输入:

10
1 1 5 4 3 6 6 5 9 10

我的输出:

35

解释:不同的三元组是

(1,3,4)

(1,3,5) (1,3,6) (1,3,9) (1,3,10) (1,4,5) (1,4,6) (1,4,9) ( 1,4,10) (1,5,6) (1,5,9) (1,5,10) (1,6,9) (1,6,10) (1,9,10) (3 ,4,5) (3,4,6) (3,4,9) (3,4,10) (3,5,6) (3,5,9) (3,5,10) (3, 6,9) (3,6,10) (3,9,10) (4,5,6) (4,5,9) (4,5,10) (4,6,9) (4,6 ,10) (4,9,10) (5,6,9) (5,6,10) (5,9,10) (6,9,10)

预期输出:

28

我得到35 triples但是28正确的答案。我的错是什么??

4

1 回答 1

0

在这种情况下,您正在计算 n! 的总可能组合!/ (n-3)!3!。但是你必须删除所有那些不是升序的三元组。

于 2012-12-23T00:46:19.887 回答