Поиск непарных чисел в массиве

Апрель 24, 2014 — Шарахов А.П.

На экзаменах и собеседованиях часто просят найти одно непарное целое число в массиве. Довольно трудной задачей считается поиск двух непарных чисел. Хотите убить препода наповал? Расскажите ему, как за один проход по элементам массива найти три непарных числа.

Не пара

Непарные числа – это числа, которые останутся после вычеркивания из массива пар одинаковых чисел. Если длина массива нечетна и заранее известно, что в нем находится не более 1 непарного числа, то совершенно ясно, что там ровно 1 непарное число. Найти его не составит большого труда – достаточно при помощи операции XOR побитно сложить по модулю 2 все числа массива. Так как парные элементы встречаются в массиве дважды, то их XOR-сумма окажется равной 0, и, следовательно, общая XOR-сумма будет равна единственному непарному элементу массива:

type
  TMyElement= integer;
  PMyElement= ^TMyElement;
  TMyArray= array of TMyElement;
  TBitInfo= record
    Mask: TMyElement;
    Sum: TMyElement;
    end;
 
const
  BitCount = SizeOf(TMyElement)*8;
  LastBitNo= BitCount-1;
 
//поиск 0..1 непарных среди Count элементов массива, начиная с p
procedure Find01(p: PMyElement; Count: integer; var Res: TMyArray);
var
  t: TMyElement;
  q: PMyElement;
begin;
  if (p=nil) or (Count<=0) or (Count and 1=0) then SetLength(Res,0)
  else begin;                                  //нечетная длина массива
    q:=p; inc(q,Count);                        //адрес за пределами массива
    t:=0;
    repeat;
      t:=t xor p^;
      inc(p);
      until p=q;
    SetLength(Res,1);                          //есть ровно 1 непарный элемент
    Res[0]:=t;
    end;
  end;

Т.к. обычное суммирование в описании следующих алгоритмов нигде не встречается, то далее везде для облегчения текста вместо 'XOR-сумма' будет использоваться термин 'сумма'.

Не пара, не пара

Если длина массива четна и заранее известно, что в нем находятся не более 2 непарных чисел, то возможны 2 варианта: в нем вообще нет непарных чисел или есть 2 непарных числа. Как и раньше, мы можем вычислить сумму всех элементов массива. Если непарные числа отсутствуют, то, очевидно, она будет равна 0. В противном случае, т.к. непарные числа отличаются хотя бы одним битом, она будет не равна 0. После того, как будет найден один единичный бит в общей сумме, мы для него дополнительно вычислим две частичных суммы: первая сумма будет содержать все элементы массива, у которых этот бит равен 1, вторая – все элементы, у которых он равен 0. Понятно, что обе суммы равны искомым непарным числам, т.к. непарные числа обязаны попасть в разные частичные суммы, а попавшие в них парные элементы взаимно уничтожатся. Заметим, что достаточно вычислять только одну частичную сумму, а вторую можно легко получить, комбинируя первую частичную сумму и общую сумму:

//поиск 0..2 непарных среди Count элементов массива, начиная с p (в 2 прохода)
procedure Find012Pass2(p: PMyElement; Count: integer; var Res: TMyArray);
var
  t, Total, Sum, Mask: TMyElement;
  q: PMyElement;
begin
  if (p=nil) or (Count<=0) then SetLength(Res,0)
  else begin;
    t:=0;
    q:=p; inc(q,Count);                        //адрес за пределами массива
    repeat;
      t:=t xor p^;
      inc(p);
      until p=q;
    if Count and 1<>0 then begin;              //нечетная длина массива, есть ровно 1 непарный элемент
      SetLength(Res,1);
      Res[0]:=t;
      end
    else if t=0 then SetLength(Res,0)          //четная длина массива, 0 непарных элементов
    else begin;                                //четная длина массива, 2 непарных элемента
      Total:=t;                                //общая сумма
      Mask:=t and -t;                          //взяли младший ненулевой бит числа t
      Sum:=0;                                  //частичная сумма
      inc(p,-Count);                           //второй проход, адрес первого элемента массива
      repeat;
        t:=p^;
        if t and Mask<>0 then Sum:=Sum xor t;
        inc(p);
        until p=q;
      SetLength(Res,2);
      Res[0]:=Sum;
      Res[1]:=Sum xor Total;
      end;
    end;
  end;

Обычно предполагается, что массив очень большой и требуется найти непарные числа за один проход по массиву, время O(N) и память O(1). Чтобы выполнить эти требования, мы можем вычислять частичные суммы для каждого бита одновременно с вычислением общей суммы, а потом из них выбрать подходящую ненулевую сумму. При этом можно обойтись даже без вычисления общей суммы:

//поиск 0..2 непарных среди Count элементов массива, начиная с p
procedure Find012(p: PMyElement; Count: integer; var Res: TMyArray);
var
  bi: array[0..LastBitNo] of TBitInfo;
  t: TMyElement;
  q: PMyElement;
  i: integer;
begin;
  if (p=nil) or (Count<=0) then SetLength(Res,0)
  else begin;
    q:=p; inc(q,Count);                        //адрес за пределами массива
    if Count and 1<>0 then begin;              //нечетная длина массива, есть ровно 1 непарный элемент
      t:=0;
      repeat;
        t:=t xor p^;
        inc(p);
        until p=q;
      SetLength(Res,1);
      Res[0]:=t;
      end
    else begin;                                //четная длина массива, 0 или 2 непарных элементов
      t:=1;
      for i:=0 to LastBitNo do begin;
        bi[i].Mask:=t; t:=t+t;                 //инициализация масок для выделения бита
        bi[i].Sum:=0;                          //иницилизация частичных сумм
        end;
 
      repeat;
        t:=p^;                                 //очередной элемент исходного массива
        for i:=0 to LastBitNo do
          if t and bi[i].Mask<>0               //если бит установлен
          then bi[i].Sum:=bi[i].Sum xor t;     //изменяем частичную сумму, бит-счетчик инвертируется
        inc(p);
        until p=q;
 
      i:=0;
      while (i<=LastBitNo) and (bi[i].Sum and bi[i].Mask=0) do inc(i); //ищем бит-счетчик, которым они различаются
      if i>LastBitNo then SetLength(Res,0)     //т.к. не нашли бит, которым различаются 2 непарных числа
      else begin;
        SetLength(Res,2);                      //иначе нашли 2 непарных числа
        Res[0]:=bi[i].Sum;
        Res[1]:=bi[i].Sum;                     //одно из них равно ненулевой частичной сумме
        repeat;                                //другое отличается от него битами, соответствующими ненулевым суммам
          if bi[i].Sum and bi[i].Mask<>0 then Res[0]:=Res[0] xor bi[i].Mask;
          inc(i);
          until i>LastBitNo;
        end;
      end;
    end;
  end;

Не пара, не пара, не пара

Если длина массива нечетна и заранее известно, что в нем находятся не более 3 непарных чисел, то также возможны 2 варианта: в нем 1 или 3 непарных числа. Как и раньше, мы можем за один проход по массиву вычислить общую сумму всех элементов массива и частичные суммы для единичного значения каждого бита.

Давайте посмотрим, чему теперь соответствуют возможные значения частичных сумм.

Случай 1. В частичной сумме для единичного значения некоторого бита этот бит принимает единичное (нечетное) значение. Очевидно, в нее вошли 1 или 3 непарных числа.

Подслучай 1а. Эта частичная сумма не равна общей сумме. Очевидно, в нее вошло 1 непарное число, равное этой сумме.

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

Случай 2. В частичной сумме для единичного значения некоторого бита этот бит принимает нулевое (четное) значение. Очевидно, в нее вошли 0 или 2 непарных числа.

Подслучай 2а. Эта частичная сумма не равна 0. Очевидно, в нее вошли 2 непарных числа, и, разумеется, они не равны друг другу.

Подслучай 2б. Эта частичная сумма равна 0. Очевидно, в нее не вошло ни одно непарное число, т.к. все они имеют нулевое значение текущего бита.

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

//поиск 0..3 непарных среди Count элементов массива, начиная с p
procedure Find0123(p: PMyElement; Count: integer; var Res: TMyArray);
var
  bi: array[0..LastBitNo] of TBitInfo;
  Total, t: TMyElement;
  q: PMyElement;
  i: integer;
begin;
  if (p=nil) or (Count<=0) then SetLength(Res,0)
  else begin;
    t:=1;
    for i:=0 to LastBitNo do begin;
      bi[i].Mask:=t; t:=t+t;                   //инициализация масок для выделения бита
      bi[i].Sum:=0;                            //иницилизация частичных сумм
      end;
 
    q:=p; inc(q,Count);                        //адрес за пределами массива
    Total:=0;                                  //общая сумма
    repeat;
      t:=p^;                                   //очередной элемент исходного массива
      Total:=Total xor t;                      //изменяем общую сумму
      for i:=0 to LastBitNo do
        if t and bi[i].Mask<>0                 //если бит установлен
        then bi[i].Sum:=bi[i].Sum xor t;       //изменяем частичную сумму, бит-счетчик инвертируется
      inc(p);
      until p=q;
 
    SetLength(Res,Count and 1);                //если длина массива нечетна, в нем есть хотя бы 1 непарный элемент
    if Count and 1<>0 then begin;              //найдем его
      i:=0;
      repeat;
        if bi[i].Sum and bi[i].Mask<>0         //если счетчик элементов нечетен - это сумма 1 или 3 непарных чисел
        then if bi[i].Sum<>Total
             then begin;                       //если в эту сумму попало ровно 1 непарное число, берем его
               Res[0]:=bi[i].Sum;              //1 непарное число найдено
               break;
               end
             else {nothing}                    //иначе у всех 3 непарных чисел этот бит = 1, продолжаем искать
        else if bi[i].Sum<>0
             then begin;                       //если в эту сумму попало 2 непарных числа, найдем третье
               Res[0]:=bi[i].Sum xor Total;    //нашли третье непарное число
               break;
               end
             else {nothing};                   //иначе у всех 1 или 3 непарных чисел этот бит = 0, продолжаем искать
        inc(i);
        until i>LastBitNo;
      if i>LastBitNo then Res[0]:=Total        //если все биты непарных чисел одинаковы - имеется всего 1 непарное число
      else for i:=0 to LastBitNo do            //иначе исключим найденное число из частичных сумм
             if Res[0] and bi[i].Mask<>0
             then bi[i].Sum:=bi[i].Sum xor Res[0];
      Total:=Total xor Res[0];                 //исключим найденное число из общей суммы
      end;
 
    if Total<>0 then begin;                    //если имеется еще 2 непарных числа
      i:=0;
      while Total and bi[i].Mask=0 do inc(i);  //ищем бит-счетчик, которым они различаются
      t:=bi[i].Sum;                            //нашли одно из этих чисел
      i:=Length(Res);
      SetLength(Res,i + 2);                    //нужно добавить еще 2 числа в результат
      Res[i]:=t;
      Res[i+1]:=t xor Total;
      end;
    end;
  end;

Все мне мало

Чтобы найти 4 непарных числа в массиве, как и в случае 3 непарных чисел потребуется прибегнуть к дополнительным рассуждениям и анализу. Пишите, если справитесь. Замечу лишь, что даже частичные суммы для единичных значений всевозможных пар битов сами по себе не особенно помогают в решении задачи. Например, массивы {1,2,4,8} и {7,14,13,11} имеют одинаковые суммы.

на главную