Как сравнить отдельные элементы в строке?

Question

Я тренируюсь на Hackerank, и я застрял на первой проблеме. Я должен писать код, который соответствует парам носков. «Например, есть n = 7 носков с цветами ar = [1,2,1,2,3,2]. Есть одна пара цвета 1 и одна пара цвета 2. Осталось три нечетных носка, один каждого цвета. Количество пар - 2. "

Ограничения задачи: 1 ≤ n ≤ 100 и 1 ≤ ar [i] ≤ 100, где 0 ≤ i

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

for(i = 0; i < n; i++)
{
    if(ar[i] == ar[i+1])
    {
         sum1 = sum1 + 1;
    }
}

if(sum1 % 2 == 1)
{
    sum1 = sum1 - 1;
}

sum1 = sum1 / 2;

Любая помощь будет оценена.

Answer 1

«Я не знаю, как написать цикл для сравнения 100 возможных цветов и иметь отдельные счетчики для каждого».

Вы можете иметь отдельные счетчики для каждого, определив массив для счетчиков. Для вас «цвета» - это целые числа, поэтому индекс массива может служить «цветом», который вы рассчитываете. Сохраненное значение (для каждого элемента в массиве) будет количеством раз, когда вы видели этот «цвет» на входе.

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

В конце этого цикла переберите ваш массив счетчиков; значение в каждом элементе скажет вам об этом "цветном" носке:

0           : no socks of that color in the input
odd number  : there are `x / 2` pairs of this color and an odd sock
even number : there are `x / 2` pairs of this color

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

Answer 2

Просто используйте массив из 100 элементов. По одному на каждый цвет.

Answer 3

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

for(int i = 0; i < n; i++){
    newAr[ar[i]]++;
}

Затем% через каждый из этих элементов.Полученный массив для вашего массива ar = [1, 2, 1, 2, 3, 2] будет иметь вид newAr = [0, 2, 3, 1, 0, 0, 0].

for(int i = 0; i < n; i++){
    numPairs += newAr[i]/2;
    if(newAr[i] % 2 == 1){
        numOddSocks++;
    }
}