Тема: Массивы
Показать сообщение отдельно
Старый 02.03.2009, 19:30   #55
HolyDel
 
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений
(для 2,707 пользователей)
Ответ: Массивы

способ 1. Без дополнительного массива. примерно квадратичная сложность.
for i = 1 to n
 cnt = 0

 if a(i)<>0
  for j = i+1 to n step -1
   if a(j) = a(i) then cnt = cnt +1
  next
 endif

 if cnt >= 3
  val = a(i)
  for j=n to i
   if a(j) = a(i) then a(j)=0
  next
 endif

next
писал в браузере - мог где нибудь накосячить

если число значений элементов массива не слишком большое. например 0..10, то можно использовать спецмассив (массив временных значений)

Способ 2. С дополнительным массивом. примерно линейная сложность.
for i = 1 to cntvals
tempcnt(i) = 0
next

for i = 1 to n
tempcnt(a(i)) = tempcnt(a(i)) + 1
next

for i = 1 to cntvals
 if tempcnt(i) >=3
  for j = 1 to n
   if a(j) = i then a(j)=0
  next
 endif
next
первый способ имеет квадратичную сложность, второй линейную. т.е. с большими массивами второй способ предпочтительнее (разумеется, если комбинация из 3х и более одинаковых значений мало)

Последний раз редактировалось HolyDel, 02.03.2009 в 20:38.
(Offline)
 
Ответить с цитированием