Нахождение потерянного элемента массива

Опубликовано Jun 6, 2013 в Манипуляция битами, Массивы и строки | 25 коммент.

, ,

Нахождение потерянного элемента массива

Имеется набор из N различных целых чисел. Из него нужно создать одномерный массив, содержащий 2*N элементов, помещая в массив каждое число из исходного набора ровно по два раза. После этого элементы массива переставляются случайным образом. Известно, что в результате этих действий РОВНО ОДИН из элементов массива потерялся, а массив оказался размерности 2*N -1. Как это выглядит можно посмотреть на рисунке.

Нужно найти испорченное значение в массиве, то есть результатами для трех приведенных вариантов повреждения данных должны быть числа 4, 4 и 5 соответственно. Желательно придумать алгоритм, который не переставляет элементы исходного массива, не портит его, не выделяет памяти под дополнительный массив и работает за один проход по исходному массиву.

 


Автор публикации:

25 Коммент. : “Нахождение потерянного элемента массива”

  1. Перепост Александра says:

    Если числа в наборе N <> 0 (или любое другое число, которого нету в исходном наборе; так же можно просто умножать на -1, а потом восстановить, если цифры в массиве нужны).

    for i:=1 to 2*N-1 do
    if a[i]<>0 then
     for j:=i+1 to 2*N do
     
      if a[i]=a[j] then 
       begin 
         a[j]:=0; j:=2*N; a[i]:=0; 
       end;
    if ((j=2*N) and (a[i]<>0)) then write (a[i]);
    if ((i=2*N-1) and (a[i+1]<>0)) then write (a[i+1]);

    Как то так, на Паскале понятней вроде.

    • Галина says:

      Паскаль… Как давно это было – я уже лет 15 не имела с ним дела, а сейчас и запускать этот код мне негде.
      Идея есть – сделан лобовой перевод кода на C#, из комментария видно, что достигнуто в правильном направлении.
      Вот перевод

        class Program
          {
              static void Main(string[] args)
              {
       
                  int[] a = { 1, 2, 3, 17, 5, 5, 4, 3, 2, 1 };
                  int N = a.Length / 2;
                  int i;
                  int j = 0;
       
                  for (i = 0; i <= 2 * N - 3; i++)
                  {
                      if (a[i] != 0)
                          for (j = i + 1; j <= 2 * N - 1; j++)
       
                              if (a[i] == a[j])
                              {
                                  a[j] = 0;
                                  j = 2 * N;
                                  a[i] = 0;
                              }
                  }
       
                  foreach (int k in a)
                      Console.Write(k.ToString() + "  "); 
                  //Здесь вывод 0 0 0 17 0 0 4 0 0 0 
                  //Из текущего состояния массива можно 
                  //получить ответ, но не так
       
                  if ((j == 2 * N) && (a[i] != 0)) { Console.WriteLine(a[i]); };
                  if ((i == 2 * N - 2) && (a[i + 1] != 0)) { Console.WriteLine(a[i + 1]); }
       
              }
          }
      }

      А замечания по решению такие.

      1. Условия, что число в исходном наборе – не ноль, нет. Поэтому основывать решение на этом допущении нельзя.
      2. В двух последних операторах if есть обращение к переменной j, которая может быть непроинициализирована по ходу алгоритма. Не помню, как на Паскале, но ни один компилятор современных языков (C#, C++, Java) такое не пропустит.
      3. Во внутреннем цикле for управляющая переменная j изменяется внутри тела цикла, помимо его заголовка. Это не рекомендуемый стиль использования данного оператора.
      4. Исходный массив портится – это всегда плохо.
      5. Имеется два вложенных цикла, следовательно, сложность алгоритма – квадратичная, а можно решить задачу с линейной сложностью.
      • Галина says:

        Ошибка с моей стороны – последнее требование при старом условии было невыполнимым. Остальное все остается в силе. При том условии, как оно написано сейчас, и последнее требование можно выполнить. Подсказка – рубрике – МАНИПУЛЯЦИЯ С БИТАМИ.

  2. Галина says:

    Прошу прощения. Отвечая на предыдущий комментарий, я сообразила, что ошиблась при формулировке условия. Ровно ОДИН элемент исходного набора при переносе в массив не ИСПОРТИЛСЯ, а ПОТЕРЯЛСЯ.

  3. Дмитрий Храмов says:

    Здравствуйте, Галина!

    Уточните, пожалуйста, правильно ли я понял ваши последние комментарии.
    1. “…последнее требование при старом условии было невыполнимым”. – речь идет о том, что требование разработки однопроходного алгоритма оказалось невыполнимым?
    2. “Ровно ОДИН элемент исходного набора при переносе в массив не ИСПОРТИЛСЯ, а ПОТЕРЯЛСЯ”. – это означает, что все элементы массива размерности 2N имеют пару, кроме одного?

    В первом случае (и не читая ваш второй комментарий :) ) становится удобно использовать сортировку. Если же я правильно истолковал ваш второй комментарий, то xor-им 2N-массив: все пары обнуляются, остается искомый элемент.

    Так или иначе, но задача демонстрирует важность общения во время собеседования :)

    • Галина says:

      1. По поводу вопроса 1 – да, именно так, как вы написали. По крайней мере для этой ситуации я однопроходного решения не знала, когда писала пост.
      2. Да, все элементы массива, кроме одного, имеют пару, а размерность массива оказалась 2N – 1.

      Дальше тоже согласна – для 2N-массива с испорченным элементом, возможно решение, основанное на сортировке. Его сложность не линейна, и оно либо требует скопировать массив, либо изменит исходный.

      Общение же важно не только на собеседовании, безусловно, но демонстрация этого обстоятельства получилась случайной :)

  4. Дмитрий Храмов says:

    Извините, только сейчас посмотрел исправленный рисунок. I’m xorry!

  5. Богдан says:

    Суммируем числа из исходного массива и умножаем на 2 (Пометим результат как А). Суммируем числа из испорченного массива (Пометим результат как Б). Потерянное число = А – Б.

    • Галина says:

      Правильно, если исходный массив имеется в распоряжении. Алгоритм однопроходный, ничего не портит, не нужна дополнительная память размером под целый массив.

  6. int n = 5;
    int original[] = {1,2,3,4,5};
    int output[] = {1,2,3,5,5,4,3,2,1};
    int sum_original = 0, sum_output = 0;
    for (int i = 0; i < 2*n-1; i++)
    {
    	if (i < n)
    	{
    		sum_original += original[i];
    	}
    	sum_output += output[i];
    }
    int missing_element = 2*sum_original - sum_output;
    • Галина says:

      Это вполне подходящие решение для идеи, которая описана постом выше.

    • Юрий says:

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

  7. Андрей says:

    если я верно понял условие, то:
    1. исходный массив отсутствует
    2. все элементы, кроме одного перенеслись дважды, один – единожды
    3. нужно найти елемент который не вошел в массив дважды, с линейной сложностью.

    можно сделать так:

    #include <iostream>
    using namespace std;
     
    int arrayCheck (int *array, int size)
    {
    int lost = 0;
    for (int i = 0; i < size; ++i)
    {
    lost = lost^array[i];
    }
    return lost;
    }
     
     
    int main()
    {
    int array[9] = {3, 5, 2, 4, 9, 2, 5, 9, 3 };
    int lostNumber = arrayCheck(array, 9);
    cout << "lost number " << lostNumber << endl;
    return 0;
    }
    • Галина says:

      Так сделать можно – это хорошее решение.

      • Сергей says:

        Я бы не сказал, что это хорошее решение. Слово “хорошее” предполагает наличие лучшего. С моей точки зрения – это самое оптимальное решение. А что, есть что-то более оптимальное, т.е. лучшее? Спасибо.

        • Галина says:

          Я была в отпуске и не отвечала. Вот, отвечаю сейчас.

          Решение правильное, все требования выполнены, лучшего варианта я не знаю (если не придираться к маленькой возможной оптимизации)

           
          int arrayCheck (int *array, int size)
          {
          	int lost = array[0];
          	for (int i = 1; i < size; ++i)
          	{
          		lost = lost^array[i];
          	}
          	return lost;
          }

          Но давать оценки в духе “самое лучшее” я обычно воздерживаюсь – как известно, совершенству нет предела.

          • Сергей says:

            Да, так сделать можно – это хорошее решение. (А маленькая оптимизация не отменяет идеи предложенного решения). Спасибо за внимание.

  8. Сергей says:

    (Мои вопросы, если Вы не возражаете – в скобках).
    Имеется набор из N различных целых чисел. Из него нужно создать(кто должен создать?) массив размерности 2*N, помещая в массив каждое число из исходного набора ровно по два раза, после чего элементы массива переставляются(кем переставляются?) случайным образом. Известно, что в результате этих действий РОВНО ОДИН из элементов массива потерялся, а массив оказался размерности 2*N -1. Как это выглядит можно посмотреть на рисунке.
    (Далее уже следует само задание, надо мне уверенно думать? Некорректность описания задания существует для более тесного и дружеского общения? Спасибо.)

  9. Я минуты две “врубался” в условие :-) Фраза “из него нужно создать массив размерности 2*N”. Массив бывает одномерным, двумерным, трехмерным (соответственно размерность массива один, два, три). Не мог никак понять. Потом посмотрел на рисунок и понял, что массив одномерный (у него размерность 1), а имеется ввиду длина одномерного массива 2*N. Так что размерность массива – это количество индексов, необходимое для идентификации его элементов.

    • Галина says:

      Правильно, спасибо за замечание – слово “размерность” не годится, исправили.

  10. c#/linq

    int[] a = { 5, 5, 4, 4, 3, 3, 2, 1, 1 };
    var r = a.GroupBy(i=>i).FirstOrDefault(g=>g.Count()==1);
    if(r != null) Console.WriteLine(r.Key);

    )

    Sincerely yours,
    Yuri Kirilenko

  11. Александр says:

    Взял массив из предыдущего примера. :)

    int[] mas = { 5, 5, 4, 4, 3, 3, 2, 1, 1 };
    int res = 0;
    foreach (int item in mas)
    {
      res = res ^ item;
    }
    Console.WriteLine(res);

Оставить комментарий

Ваш адрес email не будет опубликован.


*