Site icon AppTractor

Задачи с собеседований: найти пропущенное число в массиве

AppTractor

Один из наиболее часто задаваемых вопросов на собеседованиях — найти пропущенное число в массиве на Java, C # или любом другом языке. Такого рода вопросы задаются не только в небольших стартапах, но и в некоторых крупнейших технических компаниях, таких как Google, Amazon, Facebook, Microsoft.

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

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

В отсортированном массиве вы можете сравнить, равно ли число ожидаемому следующему числу или нет.

Кроме того, вы также можете использовать BitSet в Java для решения этой проблемы — надо перебрать все записи и использовать набор битов, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит. Запись с битом 0 является отсутствующим номером.

Найти пропущенное число в массиве: решение на Java

import java.util.Arrays;
import java.util.BitSet;
 
public class MissingNumberInArray {
 
    public static void main(String args[]) {

        // one missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6}, 6);
 
        // two missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
 
        // three missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
 
        // four missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 9, 8}, 10);
 
        // Only one missing number in array
        int[] iArray = new int[]{1, 2, 3, 5};
        int missing = getMissingNumber(iArray, 5);
        System.out.printf("Missing number in array %s is %d %n",
                           Arrays.toString(iArray), missing);
    }


   /**
    * A general method to find missing values from an integer array in Java.
    * This method will work even if array has more than one missing element.
    */
    private static void printMissingNumber(int[] numbers, int count) {
        int missingCount = count - numbers.length;
        BitSet bitSet = new BitSet(count);
 
        for (int number : numbers) {
            bitSet.set(number - 1);
        }
 
        System.out.printf("Missing numbers in integer array %s, with total number %d is %n",
        Arrays.toString(numbers), count);
        int lastMissingIndex = 0;

        for (int i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
 
    }




   /**
    * Java method to find missing number in array of size n containing


    * numbers from 1 to n only.
    * can be used to find missing elements on integer array of


    * numbers from 1 to 100 or 1 - 1000
    */
    private static int getMissingNumber(int[] numbers, int totalCount) {
        int expectedSum = totalCount * ((totalCount + 1) / 2);
        int actualSum = 0;
        for (int i : numbers) {
            actualSum += i;
        }
 
        return expectedSum - actualSum;
    }
 
}




Алгоритм с XOR


Мы можем использовать свойство XOR, чтобы получить решение этой проблемы, не беспокоясь о проблеме переполнения битов. Кроме того, XOR безопаснее и быстрее суммирования. Мы знаем свойство XOR, что XOR двух одинаковых чисел равен 0 ( A XOR A = 0). Если мы вычислим XOR всех чисел от 1 до N (это включает в себя неизвестное пропущенное число), а затем с этим результатом, XOR всех заданных чисел, общие числа будут отменены (так как A XOR A=0), и в конце мы получим пропущенное число. Если у нас нет проблемы переполнения битов, мы можем использовать как суммирование, так и алгоритмы на основе XOR, чтобы получить решение. Но алгоритм, использующий XOR, безопаснее и быстрее, чем алгоритм, который использует суммирование, вычитание и умножение. И мы можем избежать дополнительных забот, вызванных суммированием, вычитанием и умножением.


long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);


long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)
{
   xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);



	


	






		

			
				Exit mobile version