更新数组的模式

Question

我有一个数组A，并且必须在每个m步之后找到数组的模式。在每一步中，数组的一个元素被改变。如何在每次更改后有效地找到模式。我用下面的代码计算初始模式：

import java.io.*; 
import java.util.*; 
import java.math.*; 

class mode { 
    public static void main(String[] args)throws IOException { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     int N = Integer.parseInt(br.readLine()); 
     long[] A = new long[N + 1]; 
     HashMap<Long, Integer> hm = new HashMap<Long, Integer>(); 
     for (long i = 0; i <= (long)N; i++) { 
      hm.put(i, 0); 
     } 
     hm.put((long)0, 0); 
     String[] s = br.readLine().split(" "); 
     for (int i = 1; i <= N; i++) { 
      A[i] = Long.parseLong(s[i - 1]); 
      int res = hm.get(A[i]) + 1; 
      hm.put(A[i], res); 
     } 
     int countM = 0; 
     long M = hm.get(A[0]); 
     for (int i = 1; i <= N; i++) { 
      if (hm.get(A[i]) >= countM) { 
       if (A[i] > M) { 
        M = A[i]; 
       } 
       countM = hm.get(A[i]); 
      } 
     } 
     System.out.println(M); 
    } 
} 

例如让初始阵列是{1，2，1，3，3，4，5，1，3，2}。然后，初始模式是3.现在我将第五个元素更改为2.现在模式变为2.再次将已更改的数组的第四个元素更改为1.模式变为1.我想在每次更改后查找模式。

Answer 1

您可以将对(number_of_occurrences, value)存储在TreeSet中，并在每次更改初始数组时更新它（最多更改2对，因此需要O(log N)时间）。答案始终是TreeSet中最大的元素（你可以使用last方法得到它）。