Как найти наименьший префикс покрытия массива в 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

Получил 100% с нижеследующим.

public int ps (int[] a)
    {
        var length = a.Length;
        var temp = new HashSet<int>();
        var result = 0;

        for (int i=0; i<length; i++)
        {
            if (!temp.Contains(a[i]))
            {
                temp.Add(a[i]);
                result = i;
            }
        }
        return result;
    }

Answer 2

Я бы сделал это

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

Answer 3

Ваш вопрос из Alpha 2010 Start Challenge платформы Codility.И вот мое решение, получившее оценку 100 .Идея проста, я отслеживаю массив счетчиков для входного массива.Обход входного массива в обратном направлении, уменьшение соответствующего счетчика, если этот счетчик становится нулевым, это означает, что мы нашли первый префикс покрытия.

public static int solution(int[] A) {
    int size = A.length;
    int[] counters = new int[size];

    for (int a : A)
        counters[a]++;

    for (int i = size - 1; i >= 0; i--) {
        if (--counters[A[i]] == 0)
            return i;
    }

    return 0;
}

Answer 4

100p

public static int ps(int[] a) {
    Set<Integer> temp = new HashSet<Integer>();
    int p = 0;
    for (int i = 0; i < a.length; i++) {
        if (temp.add(a[i])) {
            p = i+1;
        }
    }
    return p;
}

Answer 5

вот мое решение в C #:

public static int CoveringPrefix(int[] Array1)
    {
        // Step 1. Get length of Array1
        int Array1Length = 0;
        foreach (int i in Array1) Array1Length++;
        // Step 2. Create a second array with the highest value of the first array as its length
        int highestNum = 0;
        for (int i = 0; i < Array1Length; i++)
        {
            if (Array1[i] > highestNum) highestNum = Array1[i];
        }
        highestNum++;   // Make array compatible for our operation
        int[] Array2 = new int[highestNum];
        for (int i = 0; i < highestNum; i++) Array2[i] = 0; // Fill values with zeros
        // Step 3. Final operation will determine unique values in Array1 and return the index of the highest unique value
        int highestIndex = 0;
        for (int i = 0; i < Array1Length; i++)
        {
            if (Array2[Array1[i]] < 1)
            {
                Array2[Array1[i]]++;
                highestIndex = i;
            }
        }
        return highestIndex;
    }

Answer 6

Вы также можете попробовать это решение

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int ps ( int[] A ) {
        Set set = new HashSet();
        int index =-1;

        for(int i=0;i<A.length;i++){
            if(set.contains(A[i])){
                if(index==-1)
                    index = i;
            }else{
                index = i;
                set.add(A[i]);
            }         
        }
        return index;
    }
}

Answer 7

Вот мое решение Objective-C для префиксного набора из Codility. 100% правильность и производительность.

Что можно изменить, чтобы сделать его еще более эффективным? (без использования кода c).

КАК ЭТО РАБОТАЕТ:

Каждый раз, когда я сталкиваюсь с числом в массиве, я проверяю, добавил ли я его в словарь.

Если это в словаре, то я знаю, что это не новый номер, поэтому не имеет значения в связи с проблемой. Если это новый номер, с которым мы еще не сталкивались, мне нужно обновить indexOftheLastPrefix до этой позиции массива и добавить его в словарь в качестве ключа.

Он использовал только один для цикла, поэтому занимает всего один проход. Код Objective-C довольно тяжелый, поэтому хотелось бы услышать о любых хитростях, чтобы сделать это быстрее. Тем не менее, он получил 100% за производительность.

int solution(NSMutableArray *A)

{

NSUInteger arraySize = [A count];
NSUInteger indexOflastPrefix=0;

NSMutableDictionary *myDict = [[NSMutableDictionary alloc] init];

for (int i=0; i<arraySize; i++)
{
    if ([myDict objectForKey:[[A objectAtIndex:i]stringValue]])
    {

    }
    else
    {
        [myDict setValue:@"YES" forKey:[[A objectAtIndex:i]stringValue]];
        indexOflastPrefix = i;
    }
}

return indexOflastPrefix;

}

Answer 8

Корректность и производительность: 100%:

import java.util.HashMap;
class Solution {

   public int solution(int[] inputArray)
   {
      int covering;
      int[] A = inputArray;
      int N = A.length;
      HashMap<Integer, Integer> map = new HashMap<>();
      covering = 0;

      for (int i = 0; i < N; i++)
      {
          if (map.get(A[i]) == null)
          {
              map.put(A[i], A[i]);
              covering = i;
          }
      }
      return covering;
  }
}

Answer 9

Это то, что я сделал в Java , чтобы достичь 100% правильности и 81% производительности, используя список для хранения и сравнения значений.

Недостаточно быстро пройти тесты random_n_log_100000 random_n_10000 или random_n_100000, но это правильный ответ.

public int solution(int[] A) {
    int N = A.length;
    ArrayList<Integer> temp = new ArrayList<Integer>();

    for(int i=0; i<N; i++){
        if(!temp.contains(A[i])){
            temp.add(A[i]);
        }
    }

    for(int j=0; j<N; j++){
        if(temp.contains(A[j])){
            temp.remove((Object)A[j]);
        }
        if(temp.isEmpty()){
            return j;
        }
    }

    return -1;
}

Answer 10

Я получил 100% с этим:

public int solution (int A[]){
    int index = -1;
    boolean found[] = new boolean[A.length];

    for (int i = 0; i < A.length; i++)
        if (!found [A[i]] ){
            index = i;
            found [A[i]] = true;
        }

    return index;    
}

Я использовал логический массив, который отслеживает элементы чтения.