2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Поиск подмассива в массиве
Сообщение06.12.2013, 17:06 


10/05/13
251
Дан массив длины n из нулей и единиц. Найти в нем подмассив макс. длины, в котором
количество единиц равно количеству нулей. Ограничение по времени и памяти O(n)
Вроде задача, простая, но я смог бы реализовать только перебор, как решить за O(n),
не знаю. Нужна ваша помощь.
Ведь, фактически, задача сводится к тому, чтобы найти два числа i и j, таких что
$ |i-j|+1 $ должно быть четным числом и
$ a[i] + a[i+1] + ... + a[j] = (|i-j|+1)/2 $

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение06.12.2013, 17:27 
Заслуженный участник


16/02/13
4105
Владивосток
На псевдоалголе, что ли, попробовать.
Код:
int s := 0, beg := 0, fin := 0, len := 0;
int b [0:n]; b [0] = 1; for i from 1 to n do b [i] := 0 od;
for i from 1 to n do
  S +:= (a [i] = 1|1|-1);
  if b [s] = 0 then b [s] := i elseif len < i - b [s] + 1 then beg := b [s]; fin := i; len := i - b [s] + 1 fi;
od

Заводим рабочий массив, где в i-й ячейке — самый ранний индекс, такой что сумма от 1 до него равна i. Надо найти самый длинный отрезок, не меняющий эту сумму.

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 09:13 
Заслуженный участник


12/08/10
1608
Можно так: Пусть $b[i]] $- разность между количеством 0 и 1 среди первых $i$ чисел. Надо найти $\max\limits_{\substack{0\le k<l \le n\\b[l]=b[k]}} |l-k|$. Это можно сделать за $n\log n$

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 09:55 
Заслуженный участник


16/02/13
4105
Владивосток
А мой способ, по-моему, линейный, вам чем-то не пнравился?

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 10:12 
Заслуженный участник


12/08/10
1608
$s$ может быть отрицательным или 0(или я вас не так понял и вы считаете только количество 1). А так да $O(n)$, я усложнил :-(

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 10:33 
Заслуженный участник
Аватара пользователя


06/04/10
3152
iifat в сообщении #796969 писал(а):
Заводим рабочий массив, где в i-й ячейке — самый ранний индекс, такой что сумма от 1 до него равна i.

Удобнее вместо числа единиц - разность числа единиц и нулей, так что рабочий массив сам индексируется целыми числами.

Но нужна пара индексов. Первый - самый ранний, второй - самый поздний - для текущего положения просмотра.

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 10:37 
Заслуженный участник


12/08/10
1608
Цитата:
второй - самый поздний - для текущего положения просмотра.

Мы и так знаем текущее положение просмотра :-)

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 10:43 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Null в сообщении #798108 писал(а):
Мы и так знаем текущее положение просмотра

И используем его для возможного увеличения второго члена пары, занумерованной текущим значением разности.

Если ещё помнить текущий рекорд, то алгоритм на каждом шаге просмотра "выдаёт" результат.

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение09.12.2013, 12:53 
Заслуженный участник


16/02/13
4105
Владивосток
Null в сообщении #798095 писал(а):
$s$ может быть отрицательным или 0
0 я учёл, а отрицательные и правда забыл.Спасибо.
Код:
int s := 0, beg := 0, fin := 0, len := 0;
int b [-n:n]; for i from -n to n do b [i] := 0 od; b [0] = 1;
for i from 1 to n do
   S +:= (a [i] = 1|1|-1);
   if b [s] = 0 then b [s] := i elseif len < i - b [s] + 1 then beg := b [s]; fin := i; len := i - b [s] + 1 fi;
od

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение31.12.2013, 21:47 
Заслуженный участник


23/07/08
10626
Crna Gora
Неужели кто-то еще знает и помнит непревзойденный и несравненный Algol 68!

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение31.12.2013, 23:07 
Заслуженный участник
Аватара пользователя


06/04/10
3152
svv в сообщении #808231 писал(а):
Неужели кто-то еще знает и помнит непревзойденный и несравненный Algol 68!
Остался текст -
"""Алголом жечь сердца людей! :wink:

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение01.01.2014, 00:10 
Заслуженный участник


16/02/13
4105
Владивосток
Первая любовь — она бессмертна :wink:

 Профиль  
                  
 
 Re: Поиск подмассива в массиве
Сообщение01.01.2014, 13:26 
Заслуженный участник


23/07/08
10626
Crna Gora
Да!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group