пропущенные номера

Question

Дан массив размером n.Он содержит числа в диапазоне от 1 до n.Каждый номер присутствует как минимум один раз, за ​​исключением 2 номеров.Найдите пропущенные числа.например.Предполагается, что массив элементов размера 5 равен 3,1,4,4,3

. Один подход -

static int k;
for(i=1;i<=n;i++)
{
  for(j=0;j<n;j++)
  {
    if(i==a[j])
      break;
   }
    if(j==n)
    {
      k++;
      printf("missing element is", a[j]);
    }

  if(k==2)
    break;}

. Другое решение может быть .. для (i = 0; i

Answer 1

Позвольте мне сначала объяснить концепцию :

Вы знаете, что сумма натуральных чисел 1 .... n равна (n * (n + 1)) / 2 . Также вы знаете сумму квадрата суммы первых n натуральных чисел 1,2 .... n равно n * (n + 1 ) * (2n + 1) /6. Таким образом, вы можете решить вышеуказанную проблему за O (n) время, используя вышеуказанную концепцию.

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

Для более детального решения посетите Найдите два повторяющихся элемента в данном массиве

Answer 2

Мне нравится метод "использовать элементы массива в качестве индексов" из ссылки .

. *1003*.

* алгоритма Algorithmist. Метод 5 (Использование элементов массива в качестве индекса). Спасибо Манишу К. Аасавату за предложениеэтот метод.

traverse the list for i= 1st to n+2 elements
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}

Единственное отличие состоит в том, что здесь он будет проходить от 1 до n.Обратите внимание, что это однопроходное решение, которое не требует дополнительного места (кроме хранения i)!

Сноска:

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

Answer 3

Используйте qsort() для сортировки массива, затем зациклите его один раз, чтобы найти пропущенные значения. Среднее время O (n * log (n)) из-за сортировки и минимальное постоянное дополнительное хранилище.

Answer 4

Я не проверял и не запускал этот код, но вы должны понять.

int print_missing(int *arr, size_t length) {
  int *new_arr = calloc(sizeof(int) * length);
  int i;
  for(i = 0; i < length; i++) {
    new_arr[arr[i]] = 1;
  }
  for(i = 0; i < length; i++) {
    if(!new_arr[i]) {
      printf("Number %i is missing\n", i);
    }
  }
  free(new_arr);
  return 0;
}

Время выполнения должно быть O (2n). Поправь меня, если я ошибаюсь.

Answer 5

Это вопрос интервью: Пропущенные номера.условие 1: массив не должен содержать дубликатов.Полное решение:

public class Solution5 {
public static void main(String[] args) {

    int a[] = { 1,8,6,7,10};
    Arrays.sort(a);
List<Integer> list = new ArrayList<>();
int start = a[0];
for (int i = 0; i < a.length; i++) {
    int ch = a[i];   
    if(start == ch) {
        start++;
    }else {
     list.add(start);
     start++;
     //must do this 
     i--;
    }
}//for
System.out.println(list);
}//main

}

Answer 6

Мы можем использовать следующий код для поиска дубликатов и пропущенных значений:

    int size = 8;
    int arr[] = {1, 2, 3, 5, 1, 3};
    int result[] = new int[size];

    for(int i =0; i < arr.length; i++)
    {
        if(result[arr[i]-1] == 1)
        {
            System.out.println("repeating: " + (arr[i]));
        }
        result[arr[i]-1]++;
    }

    for(int i =0; i < result.length; i++)
    {
        if(result[i] == 0)
        {
            System.out.println("missing: " + (i+1));
        }
    }

Answer 7

**

 for(i=0; i < n;i++) 
{   

while((a[i]!=i+1)&&(a[i]!=a[a[i]-1])
{

swap(a[i],a[a[i]-1]); 
} 

for(i=0;i< n;i++) 
{ 
if(a[i]!=i+1) 
printf("%d is missing",i+1); } 
this takes o(n) time    and o(1) space

======================================= **

Answer 8

используя массив поддержки, вы можете архивировать O (n)

int support[n];

// this loop here fills the support array with the
// number of a[i]'s occurences
for(int i = 0; i < n; i++)
    support[a[i]] += 1; 

// now look which are missing (or duplicates, or whatever)
for(int i = 0; i < n; i++)
    if(support[i] == 0) printf("%d is missing", i);

Answer 9

Я вижу ряд проблем с вашим кодом.Во-первых, j==n никогда не произойдет, и это не даст нам пропущенное число.Вы также должны инициализировать k до 0, прежде чем пытаться увеличить его.Я написал алгоритм, похожий на ваш, но он работает правильно.Однако, это не так быстро, как вы ожидали:

int k = 0;
int n = 5;
bool found = false;
int a[] = { 3, 1, 4, 4, 3 };

for(int i = 1; i <= n; i++)
{
  for(int j = 0; j < n; j++)
  {
    if(a[j] == i)
    {
        found = true;
        break;
    }
  }
  if(!found)
  {
      printf("missing element is %d\n", i);
      k++;
      if(k==2)
        break;
  }
  else
      found = false;
}

H2H

Answer 10

Вот, пожалуйста. Решение C #:

static IEnumerable<int> FindMissingValuesInRange( int[] numbers )
{
  HashSet<int> values = new HashSet<int>( numbers ) ;

  for( int value = 1 ; value <= numbers.Length ; ++value )
  {
    if ( !values.Contains(value) ) yield return value ;
  }
}