Подтвердить что ты не робот

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

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

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

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

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

.... Ват сказал? Или больше решений

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Обновление

Это, вероятно, клост, наиболее эффективный в 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 сделает немного более читаемый код.

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

Ответ 2

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

Возможно, более эффективно (по крайней мере, он использует меньше памяти), чтобы преобразовать строку в массив char, отсортировать массив и затем рассчитать частоты, используя простой цикл. Однако теоретически он менее эффективен (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;
    }

}

Ответ 3

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

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");
        }
    }
}

Ответ 4

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

который вы хотите узнать частоту: "_"
Строка "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;

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

Ответ 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;

}

}

Ответ 6

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

Java8 однострочная.

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