Меню
Что нового?

Задачка

Gas

может по одной?
А у гугля
Нажмите для раскрытия...
к гуглу стоит очередь из олимпиадников и просто сильно не глупых людей, они могут себе позволить любые собеседования, чтоб отобрать лучших.
А когда подобным начинают увлекаться noname-конторы за среднюю ЗП, да, выглядит странно (HraKK, это я не тебя имею ввиду)
 
zerkms

zerkms

TDD infected
Команда форума
А расскажите как гугловая задача решается :)
 
akruteckij

akruteckij

Новичок
А что если массив сперва отсортировать? И тогда получится:
PHP: 
  $itemprev;
  $arr = array("yes", "hello", "yes", "world", "hello");
  sort($arr);
  foreach ($arr as $item) {
    if (!isset($itemprev)) {
      $itemprev = $item;
    } else {
      if ($itemprev != $item) {
        echo $itemprev.'<br>';
        $itemprev = $item;
      }
      else
        unset($itemprev);
    }
  }
  if (isset($itemprev))
    echo $itemprev;
Хотя как-то громоздко получилось ((( , но зато выбирает все уникальные вхождения )))
 
zerkms

zerkms

TDD infected
Команда форума
akruteckij
Если у тебя массив отсортированный - тогда удобнее обходить for'ом с шагом +2 и сразу сравнивать пару.
 

Вурдалак

Продвинутый новичок
Хехе, а ведь если чисто числа, но можно отсортировать при определённых условиях за O(n).
 
zerkms

zerkms

TDD infected
Команда форума
Вурдалак
Эм, какой это метод сортировки даёт Θ(n) при любом входном массиве?
 
akruteckij

akruteckij

Новичок
zerkms
парами не удобно, так как могут два уникальных сразу попасть в пару и придётся делать дополнительные проверки...
 
zerkms

zerkms

TDD infected
Команда форума
akruteckij
А т.е. твои два вложенных сравнения и временная переменная - это удобно? :)
 
zerkms

zerkms

TDD infected
Команда форума
tz-lom
Мы уже обсуждаем задачу гугла, на которую сослались на предыдущей странице, там уников два.

Ну по крайней я думаю, что мы обсуждаем именно ту задачу )))
 

Вурдалак

Продвинутый новичок
zerkms написал(а):
какой это метод сортировки даёт Θ(n) при любом входном массиве?
Нажмите для раскрытия...
— не при любом, но если, к примеру, числа ограничены каким-то числом разрядов, то возможна карманная сортировка. Правда там будет большой постоянный коэффициент, но всё равно линейная зависимость получается. Сортировка подсчётом тоже могла бы подойти, если диапазон чисел заранее известен и не является большим. Я ж говорю — при определённых условиях.)

А все универсальные сортировки (сравнением) будут минимум O(n ln n).
 
akruteckij

akruteckij

Новичок
Вот новый вариант :)
PHP: 
$arr = array(38, 95, 10, 8, 95, 38, 10);
  function clearArr (&$a)
  {
    $n = count($a);
  	for($i=0; $i<$n-1; $i++)
  	{
  		for ($j=$i; $j<$n; $j++)
        if ($a[$i] == $a[$j] && $i != $j) {
          unset($a[$i]);
          unset($a[$j]);
        }
  	}
  }
  clearArr($arr);
  print_r($arr);
Тут просто немного подправил сам алгоритм сортировки и прямо в нём убрал все дублирующиеся значения...
 

Mols

Новичок
Чет я не пойму. Вот вроде всё просто...
PHP: 
$arrSource = array(.......);
$arrResult = array();
foreach($arrSource as $v) {
    if(isset($arrResult[$v])) {
         unset($arrResult[$v];
    } else {
         $arrResult[$v] = $v;
    }
}
И собсно всё вроде... пофиг сколько уников. (понятно, что с null будут приколы, но вроде есть ограничение, что числа ведь)

З.Ы.
Но задачу от гугла я не увидел если честно...
 

Mols

Новичок
Кстати насчет "обхода парами по сортированному массиву" тоже весело будет, если уники окажутся в первом(х) элементе(ах).
 

Вурдалак

Продвинутый новичок
Mols, в общем случае поиск по хеш-таблице не O(1). В этом и проблема, наверное. Хотя для практики в самый раз.
 

Mols

Новичок
tz-lom
Да может и ни в чем. В любом случае надо описывать поведение, когда наткнёмся на разные элементы.
Мне почему то показалось, что наличие такой ситуации в самом начале может добавить лишнего головняка.
Но я не уверен. А подробно думать лом))) Может я и не прав и разницы в алгоритме поведения не будет никакой (или почти никакой)
 
Войдите или зарегистрируйтесь для ответа.
Сверху