Блог

Я получил следующий вопрос во время интервью.

Вопрос: Вам нужно найти наиболее частый элемент в массиве. Массив состоит из целых чисел. Например, если у вас есть последовательность таких целых чисел: 1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2, решением будет строка:

Победителем является номер 3, его частота встречаемости составляет 6

И ответ на этот вопрос совершенствовался во время собеседования.

Ниже приведен исходный код:

 import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class RepeatedElement {

public static void main(String[] args) {
    int[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
    
    Arrays.sort(arr);
    
    int len = arr.length;
    
    int count = 1;
    
    Map<Integer,Integer> map = new TreeMap<>();
    
    int i=0;
    while(i < len) {
        for(int j=i 1;j<len;j  ) {
            if(arr[i]==arr[j]) {
                count  ;
                i  ;
            }else {
                break;
            }
        }
        map.put(arr[i], count);
        count = 1;
        i  ;
    }
    
        
    int max = 0;
    int key = 0;
    for(int k:map.keySet()) {
        int temp = map.get(k);
        
        if(temp>max) {
            max = temp;
            key = k;
        }
    }
    
    System.out.println("Winner is: " key " and it's occurrences: " max);
}
}
 

Я также искал другие подобные вопросы в stackoverflow. Я просто хочу понять, является ли это хорошим подходом к решению этой проблемы. Я считаю, что код лучше объясняет подход, который я пробовал. В то же время мне любопытно узнать о сложности времени и пространства, которая обеспечит больший вклад. Люди, пожалуйста, поделитесь своими идеями по улучшению этого кода, если в нем есть какие-то недостатки. Заранее спасибо.

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

     for (int i=0; i < arr.length; i  ) {
        map.compute(arr[i], (k,v) -> v == null ? 1 : v 1);
    }
 

В качестве альтернативы, если вы открыты для сторонних библиотек, вы можете использовать тип пакета из коллекций Eclipse и заменить весь метод следующим:

 public static void main(String[] args) {
    Integer[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
    MutableBag<Integer> bag = Bags.mutable.of(arr);
    ObjectIntPair<Integer> top = bag.topOccurrences(1).getFirst();
    System.out.println("Winner is: " top.getOne() " and it's occurrences: "  top.getTwo());
}
 

Существует даже примитивный тип мешка, чтобы избежать бокса int :

 public static void main(String[] args) {
    int[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
    MutableIntBag bag = IntBags.mutable.of(arr);
    IntIntPair top = bag.topOccurrences(1).getFirst();
    System.out.println("Winner is: " top.getOne() " and it's occurrences: "  top.getTwo());
}
 

Из этого утверждения map.put(arr[i], count); в вашем коде следует , что вы, похоже, не осознаете тот факт, что вы можете использовать существующее значение для обновления существующего ключа на вашей карте. Вот почему вы, кажется, подсчитываете элемент, повторяя все ключи. Вы можете использовать map.put(arr[i], map.get(arr[i]) 1) для обновления количества ключей, как только снова увидите ключ.

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

Код будет :

     public static void main(String args[]) {
      int[] arr = {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2};
      Map<Integer,Integer> map = new HashMap<>();
      int max = 1;
      int maxKey = arr[0];
      for ( int k : arr ) {
          map.put(k, map.getOrDefault(k, 0)   1);
          if ( map.get(k) > max ) {
              max = map.get(k);
              maxKey = k;
          }
      }
      System.out.println("Winner is: "  maxKey " and it's occurrences: " max);
   }
 

Вы выполняете сортировку: нет необходимости вводить временную сложность >= O(NLogN)

Также нет необходимости использовать карту деревьев. Вместо этого используйте хэш-карту, чтобы уменьшить операции get или put до константы вместо log(N).

Вы можете объединить две петли в одну.

Сложность решения ниже:

1. Временная сложность в приведенном ниже коде равна O(N).
2. Сложность пространства равна O(N).

Используйте map.compute (Java 8 ) для увеличения существующего количества частот. Таким образом, вам НЕ нужно

1. сначала получите существующее значение,
2. проверьте, существует ли он и увеличивается ли он, или установите значение 1, если нет.

Вы также можете использовать операцию map.merge (Java 8 ).

Примеры как слияния, так и вычисления приведены в приведенном ниже коде.

 import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class MostFrequentElementInArray {

    public static void main(String[] args) {
    int[] arr = { 1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2 };

    int len = arr.length;


    int mostFreqKey = arr[0];

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

    for (int elem : arr) {
        // you can use any of the 3:
        int newVal = map.compute(elem, (K, oldVal) -> oldVal == null ? 1 : oldVal   1  );
        // int newVal = map.merge(elem, 1, (oldVal, valWhichIs1) -> oldVal   valWhichIs1);
        // int newVal = map.merge(elem, 1, Integer::sum);
        if (map.get(mostFreqKey) < newVal) {
            // this is the new frequently occurring element
            mostFreqKey = elem;
        }
        
        
    }
    
    
    
    System.out.println("Winner is: "   mostFreqKey   " and it's occurrences: "   map.get(mostFreqKey));
    }
}