问InterviewStreet三重态优化
EN

Code Review用户

提问于 2013-01-10 11:13:58

回答 1查看 1.9K关注 0票数 1

我想出了一个采访街问题“三重态”的解决方案

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

它成功地通过了9个测试用例的15。但我的解决方案超过了时间限制，在其他测试用例。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author Dumindu
 */
public class Triplets {
    public static void main(String args[])
    {
        int[] arr,helper;
        Scanner scn=new Scanner(System.in);
        int x=scn.nextInt();
        arr=new int[x];
        helper=new int[x];
        for(int i=0;i<x;i++)
        {
            arr[i]=scn.nextInt();
        }
        int triplets=0;
        helper[0]=0;
        Map<Integer,Integer> map1=new HashMap<Integer,Integer>();

        for(int i=0;i<x;i++)
        {
            int minVals=0;

            Set<Integer> set=new HashSet<Integer>();
            int tempTrip=0;
            for(int j=i-1;j>=0;j--)
            {   
                if(arr[j]<arr[i] && !set.contains(arr[j]))
                {
                    minVals++;
                    tempTrip+=helper[j];
                    set.add(arr[j]);
                }
            }
            helper[i]=minVals;
            if(!map1.containsKey(arr[i]))
            {
                triplets+=tempTrip;
                map1.put(arr[i],tempTrip);
            }
            else
            {
                triplets=triplets-map1.get(arr[i])+tempTrip;
            }
        }
        System.out.println(triplets);
    }

}

如果有方法优化这个解决方案或以不同的方式处理它，请告诉我。

java

algorithm

回答 1

Code Review用户

发布于 2013-01-17 07:29:38

我发现很难理解您的解决方案，我编写了另一个解决方案，它首先创建所有的三胞胎，也可能是一些重复的。然后，我对三胞胎进行排序，以便重复“在一起”，然后删除重复项。

我想找一种不产生这些重复的算法，所以不需要将所有的三胞胎保存在内存中，但是我还没有找到一个解决方案：

不管怎么说，这就是我所做的：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Solution {

    public static void main(String... args) {

        Scanner scanner = new Scanner(System.in);
        int elements = scanner.nextInt();
        int[] sequence = new int[elements];

        for (int i = 0; i < elements; i++) {
            sequence[i] = scanner.nextInt();
        }

//        sequence[0] = 1;
//        sequence[1] = 1;
//        sequence[2] = 2;
//        sequence[3] = 2;
//        sequence[4] = 3;
//        sequence[5] = 4;

        List<int[]> triplets = new ArrayList<>();
        for (int i = 0; i < elements; i++) {
            int first = sequence[i];
            for (int j = i; j < elements; j++) {
                int second = sequence[j];
                if (second > first) {
                    for (int k = j; k < elements; k++) {
                        int third = sequence[k];
                        if (third > second) {
                            triplets.add(new int[] { first, second, third });
                        }
                    }
                }
            }
        }

        Collections.sort(triplets, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                int index = 0;
                int result = 0;
                int length = Math.min(o1.length, o2.length);
                do {
                    result = Integer.compare(o1[index],o2[index]);
                } while (result == 0 && ++index < length);



                return result;
            }

            @Override
            public Comparator<int[]> reverse() {
                throw new UnsupportedOperationException();
            }

            @Override
            public Comparator<int[]> compose(Comparator<? super int[]> other) {
                throw new UnsupportedOperationException();
            }
        });

        int tripletsNb = 0;
        int[] currentTriplet = null;
        for (int[] t : triplets) {
            // count non-duplicate triplets
            if (!Arrays.equals(currentTriplet, t)) tripletsNb++;
            currentTriplet = t;
            // System.out.println(Arrays.toString(t));
        }

        System.out.println(tripletsNb);
    }

}

票数 1

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/20401

复制

相似问题

问InterviewStreet三重态优化
EN

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问InterviewStreet三重态优化EN

回答 1

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问InterviewStreet三重态优化
EN