Кодичность абсолютного отличного подсчета от массива

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

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

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

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

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

вот мой код

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

    }

}

Ответ 1

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

EDIT: IMHO HashMap/HashSet - это O (log (log (n)) из-за столкновений, только O (1), если есть совершенная хэш-функция. Я бы подумал, что не создавайте объект, который будет намного быстрее но на моей машине работает только 4 раза.

В итоге вы можете видеть, что использование набора проще, понятнее и проще в обслуживании. Это все еще очень быстро и будет лучшим решением в 98% случаев.

public static void main(String[] args) throws Exception {
    for (int len : new int[]{100 * 1000 * 1000, 10 * 1000 * 1000, 1000 * 1000, 100 * 1000, 10 * 1000, 1000}) {
        int[] nums = new int[len];
        for (int i = 0; i < len; i++)
            nums[i] = (int) (Math.random() * (Math.random() * 2001 - 1000));
        Arrays.sort(nums);

        long timeArray = 0;
        long timeSet = 0;
        int runs = len > 1000 * 1000 ? 10 : len >= 100 * 1000 ? 100 : 1000;
        for (int i = 0; i < runs; i++) {
            long time1 = System.nanoTime();
            int count = countDistinct(nums);
            long time2 = System.nanoTime();
            int count2 = countDistinctUsingSet(nums);
            long time3 = System.nanoTime();
            timeArray += time2 - time1;
            timeSet += time3 - time2;
            assert count == count2;
        }
        System.out.printf("For %,d numbers, using an array took %,d us on average, using a Set took %,d us on average, ratio=%.1f%n",
                len, timeArray / 1000 / runs, timeSet / 1000 / runs, 1.0 * timeSet / timeArray);
    }
}

private static int countDistinct(int[] nums) {
    int lastLeft = Math.abs(nums[0]);
    int lastRight = Math.abs(nums[nums.length - 1]);
    int count = 0;
    for (int a = 1, b = nums.length - 2; a <= b;) {
        int left = Math.abs(nums[a]);
        int right = Math.abs(nums[b]);
        if (left == lastLeft) {
            a++;
            lastLeft = left;
        } else if (right == lastRight) {
            b--;
            lastRight = right;
        } else if (lastLeft == lastRight) {
            a++;
            b--;
            lastLeft = left;
            lastRight = right;
            count++;
        } else if (lastLeft > lastRight) {
            count++;
            a++;
            lastLeft = left;
        } else {
            count++;
            b--;
            lastRight = right;
        }
    }
    count += (lastLeft == lastRight ? 1 : 2);
    return count;
}

private static int countDistinctUsingSet(int[] nums) {
    Set<Integer> s = new HashSet<Integer>();
    for (int n : nums)
        s.add(Math.abs(n));
    int count = s.size();
    return count;
}

печатает

Для 100 000 000 номеров, используя массив, в среднем было 279 623 нас, с использованием набора в среднем было 1 270 029 нас, соотношение = 4,5

Для 10 000 000 номеров, используя массив, в среднем было 28,525 нас, с использованием набора в среднем было 126 591 нас, соотношение = 4,4

Для 1 000 000 номеров с использованием массива в среднем было 2,846 нас, с использованием набора в среднем было 12131 нас, соотношение = 4.3

Для 100 000 номеров с использованием массива в среднем было 297 нас, с использованием Set в среднем было 1 239 us, соотношение = 4.2

Для 10 000 номеров, используя массив, в среднем было 42 нас, с использованием набора в среднем было 156 нас, соотношение = 3,7

Для 1000 номеров с использованием массива в среднем было 8 us, используя Set в среднем 30 us, ratio = 3.6

В точке @Kevin K даже Integer может иметь столкновение даже через его хеш-значения, уникальные, он может отображаться в том же ведре, что и емкость.

public static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

public static void main(String[] args) throws Exception {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(32, 2.0f);
    for (int i = 0; i < 10000 && map.size() < 32 * 2; i++) {
        if (hash(i) % 32 == 0)
            map.put(i, i);
    }
    System.out.println(map.keySet());
}

печатает

[2032, 2002, 1972, 1942, 1913, 1883, 1853, 1823, 1763, 1729, 1703, 1669, 1642, 1608, 1582, 1548, 1524, 1494, 1456, 1426, 1405, 1375, 1337, 1307, 1255, 1221, 1187, 1153, 1134, 1100, 1066, 1032, 1016, 986, 956, 926, 881, 851, 821, 791, 747, 713, 687, 653, 610, 576, 550, 516, 508, 478, 440, 410, 373, 343, 305, 275, 239, 205, 171, 137, 102, 68, 34, 0]

Значения находятся в обратном порядке, потому что HashMap сгенерирован в LinkedList.

Ответ 2

Вы должны обратить внимание на то, что массив отсортирован в порядке возрастания.

Предположим, что есть только положительные числа или вопрос не о абсолютном.

Вы можете подсчитать число, итерируя по списку и увеличивая счетчик на единицу, если фактический элемент отличается от последнего. (и +1 для первого элемента)

Если вы это понимаете, вы можете добавить ограничение абсолютное. Например, улучшая алгоритм двумя указателями, один начиная с начала, один с конца. Тогда вы также должны позаботиться о том, чтобы оба указателя работали как параллельно, так что оба указателя заканчиваются на 0 или самое низкое число абсента (положительное/отрицательное). Это немного усложнит весь материал, но это возможно.

Ответ 3

Вот простое решение для этого.

public class test{

public static int dis(Integer[] arr) {
    out.println(Arrays.asList(arr));
    if (arr.length == 0) {
        return 0;
    }
    int i = 0;
    int j = arr.length - 1;
    int c = 0;
    while (i <= j) {
        if ((j != arr.length - 1) && (Math.abs(arr[j]) == Math.abs(arr[j + 1]))) {
            out.println("skipping J==" + j);
            j--; continue;
        }
        if ((i != 0) && (Math.abs(arr[i]) == Math.abs(arr[i - 1]))) {
            out.println("skipping I==" + i);
            i++; continue;
        }
        if (Math.abs(arr[i]) < Math.abs(arr[j])) {
            j--;
            c++;
        }
        else if (Math.abs(arr[i]) > Math.abs(arr[j])) {
            i++; c++;
        }
        else {
            i++; j--; c++;
        }

        out.println("I=" + i + " J=" + j + " C=" + c);
    }
    return c;
}




public static void main(String[] arg){

//Integer[] a = {34,2,3,4,3,-2,3};
//out.println("distinct elements are" + dis(a));
Integer[] aa={-5,-3,0,1,3};
out.println("distinct elements count " + dis(aa));
Integer[] ab={-5,-3,0,1,3, 4, 6, 7};
out.println("distinct elements count " + dis(ab));
Integer[] ac={-5};
out.println("distinct elements count " + dis(ac));
Integer[] acc={9};
out.println("distinct elements count " + dis(acc));
Integer[] ad={9,9,9};
out.println("distinct elements count " + dis(ad));
Integer[] ae={-5,-5};
out.println("distinct elements count " + dis(ae));
Integer[] aee={1,5,5,5,5};
out.println("distinct elements count " + dis(aee));
Integer[] af={-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8};
out.println("distinct elements count " + dis(af));

}

}

out put

[-5, -3, 0, 1, 3]
distinct elements count 4
[-5, -3, 0, 1, 3, 4, 6, 7]
distinct elements count 7
[-5]
distinct elements count 1
[9]
distinct elements count 1
[9, 9, 9]
distinct elements count 1
[-5, -5]
distinct elements count 1
[1, 5, 5, 5, 5]
distinct elements count 2
[-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8]
distinct elements count 8

Ответ 4

вот предложение python, которое я только что сделал для практики:

def abs_distinct(A):
    if not A:
        return -1
    #assume A is sorted
    n = len(A)
    left_cursor = 0
    right_cursor = n-1
    left_value = A[0]
    right_value = A[n-1]
    nb_abs_distinct = len(set([abs(left_value),abs(right_value)]))

    while left_value != right_value:
        # case 1: decrease right_cursor down to the next different value
        if abs(left_value) < abs(right_value):
            while A[right_cursor] == right_value:
                right_cursor -= 1
            right_value = A[right_cursor]
            if abs(right_value) != abs(left_value):
                nb_abs_distinct += 1
        # case 2: increase left_cursor to the next different value
        elif abs(left_value) > abs(right_value):
            while A[left_cursor] == left_value:
                left_cursor += 1
            left_value = A[left_cursor]
            if abs(left_value) != abs(right_value): 
                nb_abs_distinct += 1

        else:
            while abs(left_value) == abs(right_value):
                left_cursor += 1
                left_value = A[left_cursor]
            nb_abs_distinct += 1

    return nb_abs_distinct

Ответ 5

int count(vector<int> &A) {

    int len = B.size();
    if (len <= 0)
        return 0;

    // make a copy and calc absolutes of all items
    vector<int> B = vector<int>(A);
    for (int i = 0; i < len; i++) {
        if (B[i] < 0) 
        B[i] = -B[i];
    }

    // and sort so we have a simple absolute count
    sort(B.begin(), B.end());

    int result = 1; //count first number always
    for (int j = 1; j < len; j++) {
        if (B[j] != B[j-1])
            result++;
    }
    return result;

}

Ответ 6

вот что я придумал, не уверен, что тот факт, что он содержит цикл for внутри while, считает это типичной ошибкой noobie.

    private int getDistict(int[] myaa) {
        int dupcount=0;
        int i = 0;
        int j = myaa.length - 1;
        while (i < j) {
    //      check neighbors 
            if(Math.abs(myaa[i]) == Math.abs(myaa[i+1])) {
                dupcount++;
                i++;
                continue;
            }
//      check the other side
            if(myaa[i] < 0) {
                for(int k = j; Math.abs(myaa[i]) <= Math.abs(myaa[k]); k-- ) {
                    if(Math.abs(myaa[i])==Math.abs(myaa[k])){
                        dupcount++;
                    }
                }               
            }
            i++;
        }
        return myaa.length - dupcount;
    }

Ответ 7

Вот что я закодировал..... Дайте мне знать, если это можно улучшить....

import java.util.Arrays;
import java.util.HashSet;

/********
Joel 
Jun 19, 2013
 ********/

public class CodilityTest {

    private int[] inputArray;
    public static int count=0;

    public void setInput(int [] givenIP){
        this.inputArray= new int[givenIP.length];
        for(int i=0; i<givenIP.length;i++)
        { inputArray[i] = givenIP[i];}
    }

    public int[] getInput(){
        return this.inputArray;
    }

    public CodilityTest(){
        count=0;
    }

    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub

        CodilityTest o_tc = new CodilityTest();

        int [] x = {1,2,-3,4,-5,-11,-2,3,-4,5};
        int [] y = new int[0];
        o_tc.setInput(x);
        o_tc.getOutput(x);
        System.out.println(count);

        CodilityTest o_tc1 = new CodilityTest();
        o_tc1.getOutput(y);     
    }

    public void getOutput(int [] givenInput)
    {
        if(givenInput == null)
        {System.out.println("Please Enter some variables Sir."); return;}

        if(givenInput.length<1)
        {System.out.println("Please Enter some variables Sir."); return; }

        if(givenInput.length < 2)
        {count+=1; return;}

        HashSet<Integer> o_hs = new HashSet<Integer>();
        for(int numCount=0; numCount<givenInput.length;numCount++)
        {           
            if(o_hs.add(Math.abs(givenInput[numCount])))
            {count+=1;}
        }

    }

}

Ответ 8

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

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

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

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

Ответ 9

Ниже вы найдете реализацию, которая намного быстрее, чем у Питера.

if (A == null || A.length == 0) {
  return 0;
} else if (A.length == 1 || A[0] == A[A.length - 1]) {
  return 1;
}

int absDistinct = 0;
int leftCurrent;
int leftNext;
int rightCurrent;
int rightPrevious;

for (int i = 0, j = A.length; i < j; ) {

  leftCurrent = A[i];
  rightCurrent = A[j];
  leftNext = A[i + 1];
  rightPrevious = A[j - 1];

  if (leftCurrent + rightCurrent == 0) {
    while (A[i] - A[i + 1] == 0) {
      i++;
    }
    while (A[j] - A[j - 1] == 0) {
      j--;
    }
    i++;
    j--;
    absDistinct++;
  } else {
    if (leftCurrent + rightCurrent < 0) {
      if (leftCurrent - leftNext != 0) {
        absDistinct++;
      }
      i++;
    } else {
      if (rightCurrent - rightPrevious != 0) {
        absDistinct++;
      }
      j--;
    }
  }
}

return absDistinct;

Распределение чисел важно. Но если будет много серий одинаковых чисел, этот алгоритм будет работать лучше. Это показывает, что сложность алгоритмов не является единственным препятствием для преодоления. Когда у вас есть алгоритм с сложностью propper, это может быть только один из вариантов. Линейная коррекция алгоритма все еще возможна. Характер ввода иногда также важен.

Ответ 10

Вот рекурсивный алгоритм, который будет возвращать абсолютные уникальные записи в списке за один проход, который находится в O (n) времени. Он опирается на то, что массив отсортирован и не использует java.util.Set.

Рассмотрим этот пример массива {-5, -5, -3,0,1,3}

Поскольку массив сортируется, один из двух элементов на обоих концах массива будет иметь абсолютное максимальное значение: -5
Опять же, поскольку массив отсортирован, если этот элемент будет иметь совпадение, он будет его соседом или соседями для нескольких совпадений.
Итак, для -5 мы делаем одну проверку со своим соседом: они равны. -5 - это дубликат, поэтому удалите его, не увеличивайте текущую общую сумму и не перезапустите.

{- 5, -3,0,1,3} Теперь мы выбираем -5, его уникальный, поэтому увеличиваем общее количество до 1, а затем удаляем его.

{- 3,0,1,3} Если у них два конца имеют одинаковые абсолютные значения, просто удалите их, это не имеет значения, до тех пор, пока его только один. Скажите сначала. Мы не увеличиваем нашу текущую итоговую сумму, так как значение, которое мы удалили, было дубликатом.

{0,1,3} Теперь мы выбираем 3, его уникальное, общее количество идет до 2.

{0,1} Выберите 1, его уникальный, общий итог 3.

{0} Размер равен 1, значение уникально, увеличивать общее число и возвращать его. 4 Правильно!

package com.codility.tests;

import java.util.ArrayList; 
import java.util.Arrays;
import java.util.List;

public class AbsDistinct {

/**
 * Count the number of absolute distinct elements in an array.
 * The array is sorted in ascending order.
 */
private static int countAbsDistinct(List<Integer> list, int count) {
    int lastIndex = list.size() - 1;
    if (lastIndex == -1) { // zero size list, terminate
        return 0;
    }
    if (lastIndex == 0) { // one element list, terminate
        return ++count;
    }
    if (Math.abs(list.get(0)) == Math.abs(list.get(lastIndex))) {
        // doesn't matter which end is removed, but to remove _only_ 1
        list.remove(0);
    } else if (Math.abs(list.get(0)) > Math.abs(list.get(lastIndex))) {
        // if different to its nighbour, its unique hence count it
        if (list.get(0) != list.get(1)) {
            count++;
        }
        // now that its been accounted for, remove it
        list.remove(0);
    } else {
        // same logic but for the other end of the list
        if (list.get(lastIndex) != list.get(lastIndex - 1)) {
            count++;
        }
        list.remove(lastIndex);
    }
    return countAbsDistinct(list, count);
}

public static void main(String[] args) {
    if (args.length == 0) { // just run the tests
        List<Integer> testList = new ArrayList<Integer>(Arrays.asList(-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8));
        List<Integer> empty = new ArrayList<Integer>();
        List<Integer> singleElement = new ArrayList<Integer>(Arrays.asList(1));
        List<Integer> sameElement = new ArrayList<Integer>(Arrays.asList(1, 1, 1, 1, 1, 1));
        System.out.println("test array: " + countAbsDistinct(testList, 0));
        System.out.println("empty array: " + countAbsDistinct(empty, 0));
        System.out.println("single element array: " + countAbsDistinct(singleElement, 0));
        System.out.println("same element array: " + countAbsDistinct(sameElement, 0));
    } else {
        List<String> argStringList = new ArrayList<String>(Arrays.asList(args));
        List<Integer> argList = new ArrayList<Integer>();
        for (String s : argStringList) {
            argList.add(Integer.parseInt(s));
        }
        System.out.println("argument array: " + countAbsDistinct(argList, 0));
    }
}
}

Ответ 11

Это моя версия. Как вы думаете?

int count(vector<int> testVector){

  for(unsigned int i = 0; i < testVector.size(); i++){
    // empty array, return 0
    if(testVector.empty()) return 0;

    // one number left, must be unique, return 1;
    if(testVector.size() == 1) return 1;

    // neighbour elements are the same, delete first element
    if(testVector[0] == testVector[1]) {
        testVector.erase(testVector.begin());
        return count(testVector);
    }

    // absolute value of first and last element identical, delete first element
    if(abs(testVector[0]) == abs(testVector[testVector.size() - 1])){
        testVector.erase(testVector.begin());
        return count(testVector);
    }

    // if absolute value of beginning is greater than absolute value of end, delete beginning, otherwise end
    if(abs(testVector[0]) > abs(testVector[testVector.size() - 1])){
        testVector.erase(testVector.begin());
    } else {
        testVector.erase(testVector.end() - 1);
    }       
    // increase counter and recurse
    return 1 + count(testVector);
  }
}

Ответ 12

class Program
{
    static int CountArray(int[] MyIntArray)
    {
        int countNum = 0;
        int[] TempIntArray = new int[MyIntArray.Length];
        for (int i = 0; i < MyIntArray.Length; i++)
        {
            TempIntArray[i] = Math.Abs(MyIntArray[i]);
        }
        var queryResults = from n in TempIntArray 
                           select n;
        countNum = queryResults.Distinct().ToArray().Length;
        return countNum;
    }

    static void Main(string[] args)
    {
        Console.WriteLine("demoX6FVFB-KX8");
        Random randomNumber = new Random();
        int[] TheArray = new int[100];
        for (int j = 0; j < TheArray.Length; j++)
        {
            TheArray[j] = randomNumber.Next(-50, 50);
        }
        int counta = Program.CountArray(TheArray);
        Console.WriteLine(counta);
    }
}

Ответ 13

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

}

Ответ 14

.NET С#:

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

Ответ 15

Кратчайшая версия здесь для временной сложности O (n) и O (1) памяти:

int countAbsDistinct(int[] A) {
    int start = 0;
    int end = A.length - 1;
    if (end == -1) { // zero size list
        return 0;
    }

    int c = 1; // at least one abs distinct for non-empty array
    while(A[start]<A[end]){
        int l = Math.abs(A[start]);
        int r = Math.abs(A[end]);
    c++;

        if (r>=l){
            while(A[end]==list.get(--end)); // move left until different value
        }
        if (l>=r){
            while(A[start]==list.get(++start)); // move right until different value
        }
    }
    if(start>end){ // if last movements made start index bigger than end
        c--;
    }
    return c;
}

Ответ 16

В случае Java метод Arrays.sort() имеет лучшую среднюю производительность. Ожидание временной сложности называется O (N * log2N). Так почему бы не использовать его?

Вот решение.

Пройдите через массив, превратите все отрицательные числа в их абсолютные числа. Например, от {-5, -3, 0, 1, 3} до {5, 3, 0, 1, 3}.
User Arrays.sort(), чтобы применить массив. Например, от {5, 3, 0, 1, 3} до {0, 1, 3, 3, 5}.
Пройдите через массив снова, если соседи не имеют того же значения, подсчитайте.

Вот источник в Java.

int countDistinct(int[] A) {

    int size = A.length;
    if(size == 0) {
        return 0;
    }
    for(int i = 0; i < size; i++) {
        if(A[i] < 0) {
            A[i] = (-1) * A[i];
        }
    }

    Arrays.sort(A);

    int count = 1;
    for(int i = 0; i < size - 1; i++) {
        if(A[i] != A[i + 1]) {
            count++;
        } 
    }

    return count;
}

Ответ 17

def solution1(A):
    indneg = -1
    lena = len(A)
    lneg = list()
    lpos = list()

    for i in range(lena-1):
        if A[i] != A[i+1]:
            if A[i] < 0:
                lneg.append(A[i])
            else:
                lpos.append(A[i])
    print(lneg)
    print(lpos)

    deltalen = 0

    for i in lneg:
        if -i in lpos: deltalen +=1

    return(len(lneg)+len(lpos)-deltalen)

Ответ 18

Довольно быстрое решение на основе двоичного поиска

import java.util.Arrays;

public class AbsoluteDistinct {

    private int absoluteDistinct(int[] a) {
        if (a.length == 0 || a.length == 1) return a.length;

        Arrays.sort(a);

        int dist = 1;
        int N = a.length;
        for (int i = 0; i < N; i++) {
            if (i + 1 == N) break;
            int temp = Math.abs(a[i]);
            if (temp == Math.abs(a[i+1])) continue;
            if (Arrays.binarySearch(a, (i + 1), N, temp) < 0) dist++;
        }

        return dist;
    }


    public static void main(String[] args) {
        //generate array of 1 Million random values
        int LIMIT = 1000000;
        int[] a = new int[LIMIT];
        for (int i = 0; i < LIMIT; i++) {
            int r = (int) (Math.random() * (LIMIT + LIMIT + 1)) - LIMIT;
            a[i] = r;
        }
        //print absolute distinct numbers 
        System.out.println(new AbsoluteDistinct().absoluteDistinct(a));
    }
}

Ответ 19

Вот мой тест ruby version 100/100 на кодовость, основанный на тестах на проверку уязвимостей, массив с одинаковыми абсолютными значениями [3, -3] или [3,3] должен возвращать 1, вот список примеров ссылка

def absolute(a)
    b = Hash.new(0)
    a.each do |x|
        x = x.abs
        b[x] += 1
    end 
    return b.size
end

Ответ 20

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

def distinct(items):
    l=0
    r=len(items)-1
    count=len( set( [abs( items[l] ),abs( items[r] )] ) )
    a=1
    b=r-1
    while(a<b):
        if items[a]==items[l]:
            a+=1
        elif items[b]==items[r]:
            b-=1
        elif abs(items[a])==abs(items[b]):
            count+=1
            l=a
            r=b
            a+=1
            b-=1
        else:
            count+=2
            l=a
            r=b
            a+=1
            b-=1
    if(abs(items[a])!=abs(items[l]) and abs(items[a])!=abs(items[r]) and abs(items[b])!=abs(items[l]) and abs(items[b])!=abs(items[r])):
        count+=1
    return count

Ответ 21

Вот код С++ для обеих реализаций с кодом, который генерирует беспорядочно отсортированный целочисленный вектор:

#include <vector>
#include <set>
#include <iostream>
#include <random>
#include <cstdlib>
using namespace std;
int main(int argc, char** argv) {

    // generate a vector with random negative and positive integers, then sort it
    // vector<int> vQ2{ -5, -4, -4, -2, 0, 3, 4, 5, 5, 7, 12, 14};
    vector<int> vQ2;
    std::default_random_engine e;
    std::uniform_int_distribution<> d(-10, 10);
    std::function<int()> rnd = std::bind(d, e);
    for(int n=0; n<10; ++n)
        vQ2.push_back(rnd());
    sort(vQ2.begin(),vQ2.end());

    // set (hashfunction) solution (hash)
    set<int> sQ2;
    for_each(vQ2.cbegin(),vQ2.cend(),[&sQ2](const int input) -> void { sQ2.insert( std::abs(input) ); } );
    cout << sQ2.size() << endl;

    // pointers-meeting-in-the-middle solution        
    int absUniqueCount = 0;
    vector<int>::iterator it1 = vQ2.begin();
    vector<int>::iterator it2 = prev(vQ2.end());
    int valueIt1Prev = *it1;
    int valueIt2Prev = *it2;
    while(valueIt1Prev <= valueIt2Prev)
    {
        ++absUniqueCount;
        while(valueIt1Prev == *it1 && abs(valueIt1Prev) >= abs(valueIt2Prev))
        {   advance(it1,1); } // using advance in case of non contiguous memory container (e.g. list)
        while(valueIt2Prev == *it2 && abs(valueIt2Prev) >= abs(valueIt1Prev))
        {   advance(it2,-1); } 
        valueIt1Prev = *it1;
        valueIt2Prev = *it2;
    }
    copy(vQ2.cbegin(),vQ2.cend(),ostream_iterator<int>(cout,",")); cout << endl;
    cout << absUniqueCount << endl;

    return 0;
}

Что дает:

6
-9,-8,-8,-8,-5,0,4,4,6,6,
6

Ответ 22

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

Ответ 23

100/100 Java O (N)

public class Distinct {

    public static int solution(int[] A) {

        Set<Integer> set = new HashSet<>();
        for (int i : A) {
            set.add(i);
        }
        return set.size();
    }
}

Ответ 24

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

A O (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, и я нашел следующие решения: для меня он работает лучше, он использует меньше места и меньше циклов процессора:

импортировать 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

Ответ 25

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

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

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

Здесь ссылка на test.

Ответ 26

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

}
}

Ответ 27

Это мое решение С#, которое получило 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;
    }
}

Ответ 28

Более Catterpalistic С# решение с оценкой 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;
}

}

Ответ 29

Хорошо, если быть абсолютно честным, вам нужно сделать лучше, чем это.

Судя по этому вопросу, я предполагаю, что список не содержит дубликатов. Опять же, очевидно, что трюк - это предварительно отсортированный список. Это означает, что хотя +5 может находиться на правом конце строки, -5 будет в левом конце строки, так как отрицательные числа сортируются в обратном порядке до их абсолютной величины.

Начните с обоих концов, работайте внутри. Если два числа равны -1 друг от друга, то это не отличается. В противном случае они отличаются друг от друга и перемещают конец, который является абсолютно большим.

Пойдите, пока не достигнете нуля, или вы не столкнетесь с следующим списком - в этом случае возьмите все оставшиеся в следующем списке как отличные.

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

Ответ 30

Решение состоит в том, чтобы использовать тот факт, что массив отсортирован. Что вы можете сделать, так это иметь два указателя, указывающих на начало и конец массива соответственно. Затем, основываясь на значении абс, уменьшите/увеличьте указатель конца/указателя начала. В то же время вам придется отслеживать повторяющиеся элементы в последовательности, подобной {3,3,3,4} (три следует учитывать один раз).

Во всех случаях это не было бы слишком сложным, я думаю, что с C 20-25 loc в C.