我如何才能找到Java中的数组中最小的覆盖preFIX？

问题描述

找到一个给定的数组的第一个覆盖preFIX。

一个非空的零索引数组A由N个整数给出。第一覆盖  阵A的preFIX是最小整数p，使得和使得每一个值，该值  发生在数组A也发生在序列。

A non-empty zero-indexed array A consisting of N integers is given. The first covering prefix of array A is the smallest integer P such that and such that every value that occurs in array A also occurs in sequence.

例如，数组A的第一个覆盖preFIX  A [0] = 2，A [1] = 2，A [2] = 1，A [3] = 0，A [4] = 1是3，因为序列A [0]，  A [1]，A [2]，A [3]等于2，2，1，0包含中发生的所有值  数组A

For example, the first covering prefix of array A with A[0]=2, A[1]=2, A[2]=1, A[3]=0, A[4]=1 is 3, because sequence A[0], A[1], A[2], A[3] equal to 2, 2, 1, 0 contains all values that occur in array A.

我的解决方案

int ps ( int[] A ) 
{
    int largestvalue=0;
    int index=0;   

    for(each element in Array){
        if(A[i]>largestvalue)
        {
            largestvalue=A[i];
            index=i;
        }
    }

    for(each element in Array)
    {
        if(A[i]==index)
            index=i; 
    }   
    return index;
}

不过，这仅适用于该输入，这不是一个通用的解决方案。

But this only works for this input, this is not a generalized solution.

推荐答案

我会做到这一点。

int coveringPrefixIndex(final int[] arr) {
    Map<Integer,Integer> indexes = new HashMap<Integer,Integer>();
    // start from the back
    for(int i = arr.length - 1; i >= 0; i--) {
        indexes.put(arr[i],i);
    }
    // now find the highest value in the map
    int highestIndex = 0;
    for(Integer i : indexes.values()) {
        if(highestIndex < i.intValue()) highestIndex = i.intValue();
    }
    return highestIndex;
}

这篇关于我如何才能找到Java中的数组中最小的覆盖preFIX？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！