Эффективный способ найти частоту символа в строке в Java: O (n)

Question

В недавнем интервью меня попросили написать программу ниже.Найти персонажа, частота которого минимальна в данной строке?Поэтому я попытался перебрать строку, используя charAt, и сохранить символ в качестве ключа в HashMap, а количество вхождений - в качестве его значения.Теперь снова я должен выполнить итерацию на карте, чтобы найти самый низкий элемент.

Есть ли более эффективный способ сделать это, поскольку очевидно, что вышеприведенный слишком интенсивен, я думаю.

Обновление и другое решение

После некоторого процесса мышления и ответов, я думаю, лучшее время, которое это может быть, - O (n).В первой итерации нам нужно будет перебирать символ String за символом, а затем сохранять их частоту в массиве в определенной позиции (символ представляет собой целое число), и в то же время у нас есть две временные переменные, которые поддерживают наименьшее количество и соответствующий символ.Поэтому, когда я перехожу к следующему символу и сохраняю его частоту в arr [char] = arr [char] +1; в то же время я проверю, имеет ли временная переменная значение больше этого значения, если да, то временная переменнаябудет этим значением, и символ будет таким же. Таким образом, я полагаю, нам не нужна вторая итерация для поиска наименьшего, а также сортировка не требуется. Я думаю,

.... Ват говорит?Или любые другие решения

Answer 1

Я бы использовал массив, а не хэш-карту. Если мы ограничены ascii, это всего лишь 256 записей; если мы используем Unicode, 64 КБ. В любом случае не невозможный размер. Кроме того, я не вижу, как вы могли бы улучшить свой подход. Я пытаюсь придумать какой-нибудь умный прием, чтобы сделать его более эффективным, но я не могу придумать какой-либо.

Мне кажется, что ответ почти всегда будет целым списком символов: все те, которые используются ноль раз.

Обновление

Это, вероятно, наиболее эффективный вариант в Java. Для удобства я предполагаю, что мы используем простую Ascii.

public List<Character> rarest(String s)
{
  int[] freq=new int[256];

  for (int p=s.length()-1;p>=0;--p)
  {
    char c=s.charAt(p);
    if (c>255)
      throw new UnexpectedDataException("Wasn't expecting that");
    ++freq[c];
  }
  int min=Integer.MAX_VALUE;
  for (int x=freq.length-1;x>=0;--x)
  {
    // I'm assuming we don't want chars with frequency of zero
    if (freq[x]>0 && min>freq[x])
      min=freq[x];
  }
  List<Character> rares=new ArrayList<Character>();
  for (int x=freq.length-1;x>=0;--x)
  {
    if (freq[x]==min)
      rares.add((char)x);
  }
  return rares;
}

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

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

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

Технически было бы быстрее создать простой массив в конце, а не ArrayList, но ArrayList делает немного более читабельный код.

Может быть, есть способ сделать это быстрее, но я подозреваю, что это близко к оптимальному решению. Мне, конечно, было бы интересно узнать, есть ли у кого-нибудь идея получше.

Answer 2

Процесс поиска частоты символов в строке очень прост.
Для ответа смотрите мой код.

import java.io.*;
public class frequency_of_char
{
    public static void main(String args[])throws IOException
    {
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int ci,i,j,k,l;l=0;
        String str,str1;
        char c,ch;
        System.out.println("Enter your String");
        str=in.readLine();
        i=str.length();
        for(c='A';c<='z';c++)
        {
            k=0;
            for(j=0;j<i;j++)
            {
                ch=str.charAt(j);
                if(ch==c)
                    k++;
            }
            if(k>0)
            System.out.println("The character "+c+" has occured for "+k+" times");
        }
    }
}

Answer 3

Я думаю, что ваш подход в теории наиболее эффективен (O (n)). Однако на практике это требует довольно много памяти и, вероятно, очень медленно.

Возможно, более эффективно (по крайней мере, использует меньше памяти) преобразовать строку в массив символов, отсортировать массив, а затем вычислить частоты с помощью простого цикла. Однако теоретически он менее эффективен (O (n log n)) из-за сортировки (если вы не используете более эффективный алгоритм сортировки).

Контрольный пример:

import java.util.Arrays;

public class Test {

    public static void main(String... args) throws Exception {
        //        System.out.println(getLowFrequencyChar("x"));
        //        System.out.println(getLowFrequencyChar("bab"));
        //        System.out.println(getLowFrequencyChar("babaa"));
        for (int i = 0; i < 5; i++) {
            long start = System.currentTimeMillis();
            for (int j = 0; j < 1000000; j++) {
                getLowFrequencyChar("long start = System.currentTimeMillis();");
            }
            System.out.println(System.currentTimeMillis() - start);
        }

    }

    private static char getLowFrequencyChar(String string) {
        int len = string.length();
        if (len == 0) {
            return 0;
        } else if (len == 1) {
            return string.charAt(0);
        }
        char[] chars = string.toCharArray();
        Arrays.sort(chars);
        int low = Integer.MAX_VALUE, f = 1;
        char last = chars[0], x = 0;
        for (int i = 1; i < len; i++) {
            char c = chars[i];
            if (c != last) {
                if (f < low) {
                    if (f == 1) {
                        return last;
                    }
                    low = f;
                    x = last;
                }
                last = c;
                f = 1;
            } else {
                f++;
            }
        }
        if (f < low) {
            x = last;
        }
        return (char) x;
    }

}

Answer 4

String s = "aaaabbbbccccdddd";
Map<Character, Integer> map = new HashMap<>();

Java8 однострочный.

s.chars().forEach(e->map.put((char)e, map.getOrDefault((char)e, 0) + 1));

Answer 5

Итерация по HashMap не обязательно плоха. Это будет только O(h), где h - это длина HashMap - количество уникальных символов - которое в этом случае всегда будет меньше или равно n. Например, "aaabbc", h = 3 для трех уникальных символов. Но, поскольку h строго меньше числа возможных символов: 255, оно является постоянным. Итак, ваш биг-о будет O(n+h), что на самом деле O(n), поскольку h является константой. Я не знаю ни одного алгоритма, который мог бы стать лучше, о-о, вы могли бы попытаться получить кучу специфических для Java оптимизаций, но здесь говорится, что я написал простой алгоритм, который находит char с самой низкой частотой. Возвращает "c" со входа "aaabbc".

import java.util.HashMap;
import java.util.Map;

public class StackOverflowQuestion {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    System.out.println("" + findLowestFrequency("aaabbc"));

}

public static char findLowestFrequency(String input) {

    Map<Character, Integer> map = new HashMap<Character, Integer>();

    for (char c : input.toCharArray())

        if (map.containsKey(c))
            map.put(c, map.get(c) + 1);
        else
            map.put(c, 0);

    char rarest = map.keySet().iterator().next();

    for (char c : map.keySet())

        if (map.get(c) < map.get(rarest))
            rarest = c;

    return rarest;

}

}

Answer 6

Я бы сделал это следующим образом, так как в нем задействовано наименьшее количество строк кода:

символ, который вы хотите знать, частота: "_"
Строка "this_is_a_test"

String testStr = "this_is_a_test";
String[] parts = testStr.split("_"); //note you need to use regular expressions here
int freq = parts.length -1;

Вы можете обнаружить, что странные вещи случаются, если строка начинается или заканчивается соответствующим символом, но я оставлю это вам, чтобы проверить это.