时间戳

首页 > 解决方案 > 加乘 | 十二月长挑战赛 2

java - 加乘 | 十二月长挑战赛 2

问题描述

输入的第一行包含一个整数 T，表示测试用例的数量。T 测试用例的描述如下。每个测试用例的第一行包含一个整数 N。第二行包含 N 个空格分隔的整数 A1,A2,...,AN。输出 对于每个测试用例，打印包含一个整数的单行——所需的对数。

Example Input
2
3
2 4 2
3
0 2 3
Example Output
1
0

我的解决方案如下所示：

class Codechef {
public static void main (String[] args) throws java.lang.Exception {
    ArrayList<Integer> resultList = new ArrayList<Integer>();
    Scanner scanner = new Scanner(System.in);
    int T;

    T = scanner.nextInt();

    for(int i = 0;  i < T; i++) {
        int N;
        N = scanner.nextInt();
        int A[] = new int[N];

        for(int j = 0; j < N; j++) {
            A[j] = scanner.nextInt();
        }

        quick_sort(A, 0, N-1);

        int pos = 0, pairs = 0;
        while(pos < A.length - 1) {
            if(A[pos] == A[pos + 1]) {
                pos += 2;
                pairs += 1;
            } else {
                ++pos;
            }
        }

        resultList.add(pairs);
    }
    for(int pairCount : resultList) {
        System.out.println(pairCount);
    }
    scanner.close();
}    
}

它成功运行示例测试用例，但提交失败，我的问题是，如果输入类似于 1 1 2 2 1，那么答案应该是什么，3？因为有 2 对 1 和 1 of 2。

此外，用于此目的的建议数据结构是什么，具有原始数据类型的 Java 需要更长的时间才能使用 40,000 个输入值来执行它。我的解决方案有什么问题

标签： javadata-structures

解决方案

要回答您的第一个问题，我会说是的，每对 1 都会单独计算，所以您会得到 3。

我认为您的代码失败了，因为您只是在排序后才计算触摸对。例如，1 1 1，您在索引 0/1 处找到第一对，但随后提前 pos += 2。这意味着您缺少另外两对 1。

由于排序，您的解决方案似乎是 O(nlogn)，但我可以想到一个 O(n) 解决方案。

int[] backing = new int [10];
for (int j = 0; j < N; j++) {
    int x = scanner.nextInt();
    backing[x]++;
}
//At this point, you have a backing array with the frequency of each integer

您将需要与此类似的东西来计算对数。它是每个整数选择 2 的频率，因为您想选择一对的每次出现。

因此，例如，如果您知道您有 5 个 1，那么您将计算： 5!/(2!*3!) = 10

推荐阅读