Возвратить повторное количество и недостающее число


Вход:

Массив из N целых чисел, содержащие числа в интервале [1,п].

Каждое целое число представляется как-то кроме одной , которая повторяется дважды и Б , который отсутствует.

Выход:

Возвращение A и B.

Пример:

Вход:[3 1 2 5 3]

Выход:[3, 4]

А = 3, Б = 4

Мой подход:

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public ArrayList<Integer> repeatedNumber(final List<Integer> A) {


   //O(n) solution
   //Store the count of all the numbers appearing in the list        
   int [] count = new int[A.size()];

   int rep_num = 0,miss = 0;

   //Increase the count at the index location 
   for( int i = 0; i < A.size(); i++ )
    {
        int ind = A.get(i);
        count[ind - 1]++;

        //
        if(count[ind - 1] == 2)
            { 
                rep_num = ind;
                break;
            }
    }

    //If the count has not been updated, then the number is missing in the array
    for(int i = 0; i < count.length; i++ )
        {
            if(count[i] == 0)
                miss = i+1;

        }

    ArrayList<Integer> num = new ArrayList<Integer>();
    num.add(rep_num);
    num.add(miss);

    return num;



}
}

У меня есть следующие вопросы:

  1. Как я могу оптимизировать мой код?

  2. Есть ли лучший способ решить этот вопрос (т. е. используя лучшую структуру данных, меньше строк кода)?

Вопрос задан о: interviewbit.com



304
0
задан 25 января 2018 в 05:01 Источник Поделиться
Комментарии
2 ответа


  • Ваше решение занимает около 25 строк, который, ИМО, очень много для этой задачи. Я предлагаю мое решение в конце.

  • int rep_num = 0,miss = 0;

Избежать объявления двух переменных в одной строке, также rep_num не соответствует в Java рекомендуется нотаций. Java использует lowerCamelCase для переменной (и способ) имя, так что вы должны писать rep_num Как repNum.
Также miss не совсем понятно, как имя переменной ИМО. Может быть, вам следует рассмотреть missingNumber.


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


Set<Integer> seen = ...
for (Integer elementFromA : a) {
if (seen.contains(elementFromA)) {
// a set can only contains one elements, thus we the current value of elementFromA is a duplicate
// let's do something with it
}
seen.add(v);
}


  • Вы должны рассмотреть этот метод в static способ, как не использовать любое поле из объекта.

Вот решение я придумал (оно должно быть примерно такое же представление, как у вас) :

public static List<Integer> repeatedNumber(final List<Integer> a) {
ArrayList<Integer> res = IntStream.range(1, a.size() + 1).boxed().collect(toCollection(ArrayList::new));

// by removing everything elements from a, we are basically doing an exclusion/disjunction
// res will now contain only the missing elements from a
res.removeAll(a);

final Set<Integer> seen = new HashSet<>();
for (Integer v : a) {
if (seen.contains(v)) {
res.add(0, v);
break;
}
seen.add(v);
}

return res;
}

Чтобы убедиться, что я не делаю ошибки, я сделал быстрый тест блок класса :

public class SolutionTest {
@Test
public void basicTest() {
List<Integer> expected = Arrays.asList(3, 4);

Assert.assertEquals(expected, Solution.repeatedNumber(Arrays.asList(3, 1, 2, 5, 3)));
}

@Test
public void testWithLastNumberModified() {
List<Integer> expected = Arrays.asList(6, 7);

Assert.assertEquals(expected, Solution.repeatedNumber(Arrays.asList(1, 2, 3, 4, 5, 6, 6)));
}

@Test
public void testWithBigList() {
List<Integer> expected = Arrays.asList(2, 3);

Assert.assertEquals(expected, Solution.repeatedNumber(Arrays.asList(11, 10, 9, 8, 7, 6, 5, 4, 2, 2, 1)));
}

@Test
public void anotherTestWithBigList() {
List<Integer> expected = Arrays.asList(6, 1);

Assert.assertEquals(expected, Solution.repeatedNumber(Arrays.asList(10, 11, 7, 8, 9, 3, 2, 6, 4, 5, 6)));
}

}

0
ответ дан 25 января 2018 в 08:01 Источник Поделиться

Есть ярлык можно предпринять, чтобы найти недостающее число после того, как вы нашли повторяющееся число. Вы можете встретить этот факт раньше, где сумма чисел от 1 до n Это n*(n+1)/2. Мы можем использовать это наряду с дублируется номер, чтобы найти недостающее число. Если сложить все числа в списке и вычитать, что ожидаемая сумма от 1 до nбольшинство терминов будет отменить, оставив вас с missing - duplicate. Вы можете себе это представить на примере:

 (1+2+3+4+5+6+7)
-(1+2+3+4+5+1+7)
=(6)-(1)

В этом примере, n это 7, дублируется номер 1, а недостающее количество-6 человек. Так вы получите Формулу expected_sum - actual_sum = missing - duplicate. Мы можем решить для missing путем добавления duplicate С обеих сторон, оставив нас с missing = expected_sum - actual_sum + duplicate! Давайте сделаем это.

Во-первых, вы можете рассчитать ожидаемую сумму от этой Формулы, n*(n+1)/2. В цикле поиска дубликатов, вы будете нуждаться, чтобы сохранить текущую сумму (и не сломать рано). После того как вы найдете сумму из своего списка и выявить повторяющиеся числа, можно вычислить недостающее число, используя формулу мы говорили о в приведенном выше примере missing = expected_sum - actual_sum + duplicate.

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

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
//O(n) solution
//Keep a record of all the numbers appearing in the list
boolean [] seen = new boolean[A.size()];

int rep_num = 0, miss_num = 0;
int expected_sum = A.size() * (A.size() + 1) / 2;
int actual_sum = 0;

//Find sum of list and identify duplicate number
for( int i = 0; i < A.size(); i++ )
{
int num = A.get(i);
if(seen[num - 1])
rep_num = num;

seen[num - 1] = true;
actual_sum += num;
}

miss_num = expected_sum - actual_sum + rep_num;

ArrayList<Integer> results = new ArrayList<Integer>();
results.add(rep_num);
results.add(miss_num);

return results;
}
}

2
ответ дан 25 января 2018 в 06:01 Источник Поделиться