Как найти наименьший префикс покрытия массива в Java?

Question

Найти первый префикс покрытия данного массива.

Дан непустой индексированный с нуля массив A, состоящий из N целых чисел. Первое покрытие Префикс массива A - это наименьшее целое число P, такое, что каждое значение встречается в массиве А также встречается в последовательности.

Например, первый префикс покрытия массива A с 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, содержит все значения, которые встречаются в массив А.

Мое решение

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;
}

Но это работает только для этого ввода, это не обобщенное решение.

Answer 1

кратчайший код возможен в Java:

    public static int solution(int A[]){
    Set<Integer> set = new HashSet<Integer>(A.length);//avoid resizing
    int index= -1; //value does not matter;
    for (int i = 0; i < A.length; i++) 
        if( !set.contains(A[i])) set.add(A[index = i]); //assignment + eval     
    return index;
}

Answer 2

    //method must be public for codility to access
public int solution(int A[]){
    Set<Integer> set = new HashSet<Integer>(A.length);
    int index= A[0];
    for (int i = 0; i < A.length; i++) {
        if( set.contains(A[i])) continue;
        index = i;
        set.add(A[i]);
    }   
    return index;
}

получено 100%, однако обнаруженное время было O (N * log N) из-за HashSet. ваши решения без хэш-наборов, на которых я действительно не следую ...

Answer 3

Это то, что я попробовал первым.Я получил 24%

public int ps ( int[] A ) {
int n = A.length, i = 0, r = 0,j = 0;

for (i=0;i<n;i++) {
    for (j=0;j<n;j++) {
        if ((long) A[i] == (long) A[j]) {
            r += 1;
        }
        if (r == n) return i;
    }
}
return -1;
}

Answer 4

Без использования любой коллекции:
поиск по индексу первого вхождения каждого элемента,
префикс является максимумом этого индекса.Сделайте это задом наперед, чтобы закончить рано:

private static int prefix(int[] array) {
    int max = -1;
    int i = array.length - 1;
    while (i > max) {
        for (int j = 0; j <= i; j++) { // include i
            if (array[i] == array[j]) {
                if (j > max) {
                    max = j;
                }
                break;
            }
        }
        i--;
    }
    return max;
}

// TEST

private static void test(int... array) {
    int prefix = prefix(array);
    int[] segment = Arrays.copyOf(array, prefix+1);
    System.out.printf("%s = %d = %s%n", Arrays.toString(array), prefix, Arrays.toString(segment));
}

public static void main(String[] args) {
    test(2, 2, 1, 0, 1);
    test(2, 2, 1, 0, 4);
    test(2, 0, 1, 0, 1, 2);
    test(1, 1, 1);
    test(1, 2, 3);
    test(4);
    test();  // empty array
}

Answer 5

int решение (вектор & A) { // напишите ваш код на C ++ 11 (g ++ 4.8.2)

int max = 0, min = -1;

int maxindex =0,minindex = 0;

min = max =A[0];

for(unsigned int i=1;i<A.size();i++)
{

    if(max < A[i] )
    {
      max = A[i];
      maxindex =i;

    } 
     if(min > A[i])
     {
         min =A[i];
         minindex = i;
     }

}

if(maxindex > minindex)
       return maxindex;
else
    return minindex;

}

Answer 6

fwiw: также получает 100% на коде, и это легко понять только с одним HashMap

public static int solution(int[] A) {
    // write your code in Java SE 8

    int firstCoveringPrefix = 0;
    //HashMap stores unique keys
    HashMap hm = new HashMap();

    for(int i = 0; i < A.length; i++){
        if(!hm.containsKey(A[i])){
            hm.put( A[i] , i );
            firstCoveringPrefix = i;
        }
    }
    return  firstCoveringPrefix;
}

Answer 7

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

    class Solution {
        public int solution(int[] A) {
            // write your code in Java SE 8
            Set<Integer> s = new HashSet<Integer>(); 
            int index = 0;
            for (int i = 0; i < A.length; i++) {
                if (!s.contains(A[i])) {
                    s.add(A[i]);
                    index = i;
                }
            }
            return index;
        }
    }