codility абсолютное отличное количество от массива

Question

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

1. подсчитывает количество элементов в массиве, которые абсолютно различны, что это означает, если массив имел -3 и 3в нем эти числа не различны, потому что | -3 | = | 3 |.я думаю, что пример прояснит это лучше

a = {- 5, -3,0,1, -3} результат будет 4, потому что в этом массиве есть 4 абсолютно разных элемента.

В вопросе также указывалось, что a.length будет <= 10000, и, что наиболее важно, указывалось, что предполагается, что массив <strong>отсортирован в порядке возрастания , но я действительно не понимал, зачем нам нужноэто будет отсортировано

ЕСЛИ ВЫ ДУМАЕТЕ, ЧТО-ТО ЧТО-ТО ЗАПРОСИЛ, И Я ПОПРОБУЮ УДАЛИТЬ ВОПРОС ДАЛЬШЕ.

здесьмой код

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


public class test2 {

    int test(int[] a){
        Set<Integer> s=new HashSet<Integer>();

        for(int i=0;i<a.length;i++){
            s.add(Math.abs(a[i]));

        }
        return s.size();

    }

    public static void main(String[] args) {
        test2 t=new test2();
        int[] a={1,1,1,2,-1};
        System.out.println(t.test(a));

    }

}

Answer 1

Очень легко сделать в Scala:

object Solution {
    def solution(A: Array[Int]): Int = {

        return(A.map(v => math.abs(v)).distinct.length)
    }
}

Вот ссылка на тест .

Answer 2

Вот реализация Python: может не слишком отличаться от принятого решения, но основана на идее двух указателей.

Answer 3

Это мое решение на c #, получившее 100/100 за производительность и правильность.Это обеспечивает простое решение проблемы.

using System;

class Solution {
    public int solution(int[] A) {
        int arrLength = A.Length;

        Array.Sort(A);

        int[] arrNegative = new int[1000002];

        int[] arrPositive = new int[1000002];

        int i,counter = 0,holder = 0;

        bool zero = false;

        for (i=0; i < arrLength; i++){     
            if(A[i]<0){
                holder = Math.Abs(A[i]);
                if(arrNegative[holder]==0) arrNegative[holder] = holder;   
            }
            else{
                if(A[i]==0) zero = true;

                if(arrPositive[A[i]]==0) arrPositive[A[i]] = A[i];
            }
        }

        foreach(int c in arrNegative){
            if(c!=0) counter++;
        }

        foreach(int c in arrPositive){
            if(c!=0) counter++;
        }

        if(zero) counter++;

        return counter;
    }
}

Answer 4

JavaScript: 100/100

function solution(A) {
    var count = 1,
        len = A.length,
        S = A.map(function(x){ return Math.abs(x) }).sort();

    for(var i=1;i<len;i++) {
        if(S[i] != S[i-1]) count++;        
    }

    return count;
}

Answer 5

Ваше решение является по крайней мере одним из самых простых способов сделать это (более читаемым, более легким в обслуживании).Это, безусловно, не самый эффективный (и не самый худший) и должен быть приемлемым, если не используется в критичном по времени коде.

Но вы должны были упомянуть об этом и предположить, что есть более эффективное решение, такое как обход списка с обоих концов (как уже ответили).Возможно, у вас было бы дополнительное очко для обсуждения преимуществ обоих решений.

Протестировано ваше решение (на старом (медленном) ноутбуке):

• менее 2 миллисекунд для 10000 номеров
• ~ 450 мс для 1000000

Answer 6

Java 100/100 https://codility.com/demo/results/demoMTWUSD-S9M/

Решение AO (N) без использования множеств и без использования Sort, вдохновленное книгой Programming Pearls, глава 1:

public int solutionWithoutSetCountUntilInputLength(int[] A) {
       int length = A.length;
       int inputLimit = 1000000;
       int[] positives = new int[inputLimit];
       int[] negatives = new int[inputLimit]; // should be length - 1 not counting zero

       for (int element : A) {
           if ( element >=0 ) {
               ++positives[element];
           } else {
               int abs = element * -1;
               ++negatives[abs];
           }
       }

       int countDistincts = 0;

       for (int i: A) {
           if (i >= 0 ) {
               if ( positives[i] >= 1 ) {
                   ++countDistincts;   
                   positives[i] = 0;
               }
           } else {
               if ( negatives[i * -1] >= 1 ) {
                   ++countDistincts;   
                   negatives[i * -1] = 0;
               }
           }
       }        
       return countDistincts ;
   }

Я былПодумав об улучшении последнего ответа, я провел некоторое исследование битовых операций с Java и обнаружил, что следующие решения для меня работают лучше, он использует меньше места и меньше циклов ЦП:

import java.util.Set;

public class Distinct {
public int solution(int[] A) {
        // first part for negatives, second part for positives and adding 1
        // to count the zero as part of the positives section
        int offset = 1_000_000;
        BitSet bitSet = new BitSet( (offset * 2) + 1 );

        for (int element : A ) {
            int index = element >= 0 ? offset + element : (element * -1);
            bitSet.set(index);
        }

        return bitSet.cardinality();
    }
}

Вот ссылка на код 100/100: https://codility.com/demo/results/demoN57YUC-G9Z/

Другие мои попытки вы можете увидеть здесь: Distinct

Answer 7

import java.util.Arrays;

public class DistinctNumbers {

    public static void main(String[] args) {

       int[][] tests = new int[][] {
                                 {-5,-3, 0, 1, 3},    //4
                                 {-5,-5,-5,-5,-5},   // 1
                                 { 1, 2, 3, 4, 5},   // 5
                                 { 1},               // 1
                                 { 1, 2},            // 2
                                 { 1, 1},            // 1
                        };

       for (int[] test : tests) {
           int count = findDistinctNumberCount( test );
           System.out.println(count);
       }

    }

    static int findDistinctNumberCount(int[] numbers) {

        // 1. make everything abs.
        for (int i=0; i<numbers.length; i++) {
          if (numbers[i] <0) {
              numbers[i] = Math.abs(numbers[i]);
          }
        }

        // 2. sort them
        Arrays.sort(numbers);

        // 3. find
        int count = numbers.length;

        for (int i=0; i<numbers.length; i++) {

            // skip if not distinct (equal)
            i = skipIfNeededAndGentNextIndex(i, numbers);

        }

        return count;

    }

    public static int skipIfNeededAndGentNextIndex(int currentIndex, int[] numbers) {

        int count = numbers.length;

        int nextIndex = currentIndex;

        if ( (nextIndex + 1) != numbers.length)  {

            nextIndex += 1;

            while(numbers[currentIndex] == numbers[nextIndex]) {

                count -= 1;

                if ( (nextIndex + 1) != numbers.length) {
                    nextIndex += 1;
                } else {
                    break;
                }

            }

        }

        return count;
    }

}

Answer 8

//java code scored 100/100 
class Solution{
public int solution(int[] A){
int distinct = 0;
Arrays.sort(A);
    if (A.length == 0){
        distinct= 0;
       }
    else{
        distinct= 1;
    }

 for(int i=1; i<A.length;i++){
    if(A[i] == A[i-1]){continue;}
    else {
    distinct +=1;
    }
}
return distinct;
}
public static void main(String[] args){
int A [] = {2,1,1,2,3,1};
System.out.println(solution(A));

}
}

Answer 9

.NET C #:

static int absoluteDistinctNumbers(int[] arr)
{
    int same = 0;
    int l = 0;
    int r = arr.Length - 1;

    while (l < r)
    {
        if (Math.Abs(arr[l]) == Math.Abs(arr[r]))
            ++same;

        if (Math.Abs(arr[l]) > Math.Abs(arr[r]))
            ++l;
        else
            --r;
    }

    return arr.Length - same; 
}

Есть ли проблема с этим решением?Это выглядит намного проще, чем другие, представленные ... и это заняло у меня около 10 минут, так что я совершенно уверен, что сделал что-то не так, но я понятия не имею, что ... Мои тесты:

var arr = new int[] { 4, 2, 1, 1, -1, -5 };
var result = absoluteDistinctNumbers(arr);
Debug.Assert(4 == result);

arr = new int[] { 1, -1 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(1 == result);

arr = new int[] { };
result = absoluteDistinctNumbers(arr);
Debug.Assert(0 == result);

arr = new int[] { 2 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(1 == result);

arr = new int[] { 3, 3, -3 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(1 == result);

arr = new int[] { 2, 0, 0, 0 };
result = absoluteDistinctNumbers(arr);
Debug.Assert(2 == result);

Answer 10

Более Catterpalistic C # решение с оценкой 100/100.

Получил советы по ссылке ниже.https://codesays.com/2014/solution-to-abs-distinct-by-codility/

 using System;

class Solution {
public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    var head = 0; 
    var tail = A.Length -1;
    var absCount = 1;
    var current = A[0] > 0 ? A[0] : -A[0];
    while(head <= tail)
    {
        var former = A[head] > 0 ? A[head] : -A[head];
        if(former == current)
        {
            head ++;
            continue;
        }

        var latter = A[tail] > 0 ? A[tail] : -A[tail];
        if(latter == current)
        {
            tail--;
            continue;
        }

        if(former >= latter)
        {
            current = former;
            head ++;
        }
        else 
        {
            current = latter;
            tail--;

        }

        absCount++;
    }

    return absCount;
}

}