“漂亮的三胞胎”问题中hackerrank的java计时问题

zqdjd7g9 于 2021-07-12 发布在 Java

关注(0)|答案(2)|浏览(270)

我正在解决“美丽的三胞胎”的问题可能是我的逻辑是正确的，但它显示了计时问题的问题是下面的图片中给出的。我的解决方法同样是下面给出的。它只包含给定的函数beautifultriplets（int d，int[]arr），它返回整数并接受两个值一个是d，另一个是整数数组。一些案例正在运行，但有些案例显示计时错误。
问题是
问题
同样的解决方案是

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the beautifulTriplets function below.
    static int beautifulTriplets(int d, int[] arr) {
        int i,j,k,beautifulTripletsCount=0;
        for(i=0;i<(arr.length-2);i++)
        {
            for(j=i+1;j<(arr.length-1);j++)
            {
                for(k=j+1;k<(arr.length);k++)
                {
                    if(i<j&& j<k)
                    {   
                        int j_i_Difference=arr[j]-arr[i];
                        int k_j_Difference=arr[k]-arr[j];
                        if(j_i_Difference==k_j_Difference && k_j_Difference==d)
                        {
                            beautifulTripletsCount++;
                        }
                    }
                }
            }

        }
        return beautifulTripletsCount;

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nd = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nd[0]);

        int d = Integer.parseInt(nd[1]);

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int result = beautifulTriplets(d, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Java

来源：https://stackoverflow.com/questions/60204114/timings-problems-in-hackerrank-in-beautiful-triplets-question

2条答案

按热度按时间

dvtswwa31#

3个嵌套循环的解决方案的运行时间为 O(n^3) .
你可以把它改进成 O(n^2) 具体如下：
让 i 从 1 至 arr.length - 2 . 找出其中美丽的三胞胎的数目 arr[i] 是中间元素：
迭代自 i-1 下到 0 计算元素的个数 arr[i] - d 迭代自 i+1 高达 arr.length - 1 计算元素的个数 arr[i] + d 把你在前两步中找到的两个数字相乘，然后把乘积加到美丽的三胞胎总数上。
这将使您的总运行时间 O(n^2) 即使输入数组没有排序。
如果对输入数组进行排序，您可以做得更好，因为步骤2。和3。可以做二进制搜索，因此采取 O(logn) 而不是 O(n) . 这将使您的总运行时间 O(nlogn) .
常规（未排序）数组的版本：

int result = 0;
for (int i = 1; i < arr.length - 1; i++) {
    int first = 0;
    int third = 0;
    for (int j = i - 1; j >= 0; j--) {
        if (arr[i] - arr[j] == k) {
            first++;
        }
    }
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] - arr[i] == k) {
            third++;
        }
    }
    result += first * third;
}

赞(0）回复(0）举报 2021-07-12

kknvjkwl2#

我改进计时的方法是做一个循环，在数组中找到索引j和k，将d加到i和j处的值上。我使用了java的二进制搜索实现。

int count = 0;
    Arrays.sort(arr);
    for (int i = 0; i < arr.length; i++) {
        int j = Arrays.binarySearch(arr, arr[i] + d);
        if (j > 0) {
            int k =Arrays.binarySearch(arr, arr[j] + d);
            if (k > 0) {
                count++;
            }
        }
    }
    return count;

赞(0）回复(0）举报 2021-07-12

我来回答

“漂亮的三胞胎”问题中hackerrank的java计时问题

2条答案

相关问题

热门标签

最新问答