How to find the smallest array coverage prefix in Java?

Question

Find the first coverage prefix for this array.

Given a non-empty null-indexed array A, consisting of N integers. The first coverage of the prefix of array A is the smallest integer P such that it is such that every value that occurs in array A is also in sequence.

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

My decision

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, it is not a generalized solution.

Answer 1

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 2

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

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 6

#:

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 7

:
,
- . , :

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 8

, . 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 9

    //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. hashsets ...

Answer 10

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 11

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

, .

Answer 12

, 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 13

: 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 14

Objective-C PrefixSet Codility. 100% .

, ? ( c).

:

, , , .

, , , . , , indexOftheLastPrefix .

It uses only one cycle, so it takes only one pass. Objective-C code is very quiet, so I would like to hear any tricks to make it faster. However, he got 100% for the performance.

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 15

int solution (vector & A) {// write your code in 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 16

fwiw: also gets 100% of the coding, and this is easy to understand with just one 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 17

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