неделя, 18 декември 2011 г.

Задача 15 - Сортиране на редица по честота на елементи

Една задача изпратена ни от rehopul:

От въведен низ от клавиатурата да се намери най-често срещаният символ и да се изведе низа по честота на срещане на символите. При еднакъв брой срещания няма значение кой символ да се изведе предварително.
Например: От низ – “ммпкдсррттмвввпмм”, най-често срещаният символ е “м”.
Низа да се изведе: “мммммвввррттппкдс”

Кратко решение на PHP, защото само това имам инсталирано в момента:



<?php
  $string = 'tabdaderdty';
  $counter = array_fill(0, 255, 0);
  for ($i = 0; $i < strlen($string); $i++) {
    $counter[ord($string[$i])]++;
  }
  arsort($counter);
  echo $string.PHP_EOL;
  foreach($counter as $k => $v){
    if ($v == 0) {
      break;
    }
    echo str_repeat(chr($k), $v);
  }
  echo PHP_EOL;
?>



Принципът е следния:
Създаваме масив с 255 елемента и стойности 0 за всеки един елемент. След това обхождаме символния низ и увеличаваме стойността на брояча за всеки срещнат масив (индекса на масива е ASCII стойността на символа). След това сортираме низходящо масива с броячите и показваме по n елемента за всяко n > 0.

$php redica.php 
tabdaderdty
dddttaaebyr

Няма коментари:

Публикуване на коментар