6

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?

Input format:

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

Output format:

A single integer that denotes the number of distinct ascending triples present in the array

Constraints:

N <= 10^5 Every value in the array is present at most twice Every value in the array is a 32-bit positive integer

Sample input:

6 
1 1 2 2 3 4

Sample output:

4

Explanation:

The distinct triplets are

(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)

Another test case:

Input:

10
1 1 5 4 3 6 6 5 9 10

Output:

28

I tried to solve using DP. But out of 15 test cases only 7 test cases passed. Please help solve this problem.

4

7 回答 7

8

您应该注意，您只需要知道小于/大于特定元素的元素数量即可知道它用作中间点的三元组数量。使用它，您可以很容易地计算三元组的数量，唯一剩下的问题是摆脱重复项，但鉴于您最多只能使用 2 个相同的元素，这很简单。

我使用二进制索引树http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees解决了。

我还写了一篇小文章，http://www.kesannmcclean.com/?p=223。

于 2012-12-19T22:50:04.437 回答
2 
package com.jai;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Triplets {

    int[] lSmaller, rLarger, treeArray, dscArray, lFlags, rFlags;

    int size, count = 0;

    Triplets(int aSize, int[] inputArray) {
        size = aSize;
        lSmaller = new int[size];
        rLarger = new int[size];
        dscArray = new int[size];
        int[] tmpArray = Arrays.copyOf(inputArray, inputArray.length);
        Arrays.sort(tmpArray);
        HashMap<Integer, Integer> tmpMap = new HashMap<Integer, Integer>(size);
        for (int i = 0; i < size; i++) {
            if (!tmpMap.containsKey(tmpArray[i])) {
                count++;
                tmpMap.put(tmpArray[i], count);
            }
        }
        count++;
        treeArray = new int[count];
        lFlags = new int[count];
        rFlags = new int[count];
        for (int i = 0; i < size; i++) {
            dscArray[i] = tmpMap.get(inputArray[i]);
        }

    }

    void update(int idx) {
        while (idx < count) {
            treeArray[idx]++;

            idx += (idx & -idx);
        }
    }

    int read(int index) {
        int sum = 0;
        while (index > 0) {
            sum += treeArray[index];
            index -= (index & -index);
        }
        return sum;
    }

    void countLeftSmaller() {
        Arrays.fill(treeArray, 0);
        Arrays.fill(lSmaller, 0);
        Arrays.fill(lFlags, 0);
        for (int i = 0; i < size; i++) {
            int val = dscArray[i];
            lSmaller[i] = read(val - 1);
            if (lFlags[val] == 0) {
                update(val);
                lFlags[val] = i + 1;
            } else {
                lSmaller[i] -= lSmaller[lFlags[val] - 1];
            }
        }
    }

    void countRightLarger() {

        Arrays.fill(treeArray, 0);
        Arrays.fill(rLarger, 0);
        Arrays.fill(rFlags, 0);
        for (int i = size - 1; i >= 0; i--) {
            int val = dscArray[i];
            rLarger[i] = read(count - 1) - read(val);
            if (rFlags[val] == 0) {
                update(val);
                rFlags[val] = i + 1;
            }
        }
    }

    long countTriplets() {
        long sum = 0;
        for (int i = 0; i < size; i++) {
            sum += lSmaller[i] * rLarger[i];
        }
        return sum;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] a = new int[N];
        String[] strs = br.readLine().split(" ");
        for (int i = 0; i < N; i++)
            a[i] = Integer.parseInt(strs[i]);
        Triplets sol = new Triplets(N, a);
        sol.countLeftSmaller();
        sol.countRightLarger();
        System.out.println(sol.countTriplets());
    }
}
于 2013-10-28T09:09:01.643 回答
1

对于我想出的暂定算法，它应该是：

(K-1)!^2

其中 K 是唯一元素的数量。

编辑

经过更多思考：

      SUM[i=1,K-2]  SUM[j=i+1,K-1]    SUM[m=j+1,K]   1
 =>   SUM[i=1,K-2]  (SUM[j=i+1,K-1]   (K-j))
于 2012-12-18T10:05:33.643 回答
1
  • 如果输入未排序（问题对此不清楚）：对其进行排序
  • 删除重复项（此步骤可以与第一步结合）
  • 现在选择 3 个项目。由于项目已经排序，因此选择的三个项目也已排序
  • IIRC 有 (n!) / ((n-3)! * 3!) 方法来选择这三个项目；与 n := 唯一项目的数量
于 2012-12-19T23:07:12.327 回答
0

python中的解决方案之一：

from itertools import combinations as comb
def triplet(lis):
    done = dict()
    result = set()
    for ind, num in enumerate(lis):
        if num not in done:
            index = ind+1
            for elm in comb(lis[index:], 2):
                s,t = elm[0], elm[1]
                if (num < s < t):
                    done.setdefault(num, None)
                    fin = (num,s,t)
                    if fin not in result:
                        result.add(fin)
    return len(result)

test = int(raw_input())
lis = [int(_) for _ in raw_input().split()]
print triplet(lis)
于 2014-02-05T15:14:12.280 回答
0

@hadron：确切地说，我无法理解为什么一组 7 个不同的数字应该是28而不是35 *

[由于问题是关于升三连音，重复的数字可以丢弃]。

顺便说一句，这是一个非常糟糕的 Java 解决方案（N^3）：

我还打印了可能的三元组：

我也在考虑一些函数，它指示输入“N”可能的三元组数

  • 4 4
  • 5 10
  • 6 20
  • 7 35
  • 8 56

  • 9 84

    包 org.HackerRank.AlgoChallenges；

    导入 java.util.Iterator；导入 java.util.Scanner；导入 java.util.TreeSet；

    公共类三胞胎{

    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int result = 0;
    int n = scanner.nextInt();
    Object[] array = new Object[n];
    TreeSet<Integer> treeSet = new TreeSet<Integer>();
    /*
     * for (int i = 0; i < n; i++) { array[i] = scanner.nextInt(); }
     */

    while (n>0) {
        treeSet.add(scanner.nextInt());
        n--;
    }
    scanner.close();

    Iterator<Integer> iterator = treeSet.iterator();
    int i =0;
    while (iterator.hasNext()) {
        //System.out.println("TreeSet["+i+"] : "+iterator.next());
        array[i] = iterator.next();
        //System.out.println("Array["+i+"] : "+array[i]);
        i++;
    }
    for (int j = 0; j < (array.length-2); j++) {
        for (int j2 = (j+1); j2 < array.length-1; j2++) {
            for (int k = (j2+1); k < array.length; k++) {
                if(array[j]!=null && array[j2]!=null && array[k]!=null){
                    System.out.println("{ "+array[j]+", "+array[j2]+", "+array[k]+" }");
                    result++;
                }
            }
        }
    }

    System.out.println(result);
}
于 2013-03-28T08:07:42.723 回答
-1

你关心复杂性吗？

输入数组是否已排序？

如果你不介意复杂性，你可以用 N^3 的复杂性来解决它。

复杂度为 N^3 的解决方案：如果未排序，则对数组进行排序。使用 3 个 for 循环一个在另一个中，然后为每个数字扔数组 3 次。使用哈希图计算所有三元组。键是它自己的三元组，值是出现的次数。

它应该是这样的：

for (i1=0; i1<N; i1++) {
    for (i2=i1; i2<N; i2++) {
        for (i3=i2; i3<N; i3++) {
            if (N[i1] < N[i2] < N[i3]) {
                /* if the triple exists in the hash then 
                        add 1 to its value
                    else 
                        put new triple to the hash with 
                        value 1 
                */
            }
        }
    }
}

结果 = 哈希中的三元组数；

我没有尝试过，但我认为它应该可以工作。

于 2012-12-18T08:38:55.747 回答