Java-lấy phần tử phổ biến nhất trong danh sách

Question

Java hoặc ổi có thứ gì đó sẽ trả về phần tử phổ biến nhất trong danh sách không?

List<BigDecimal> listOfNumbers= new ArrayList<BigDecimal>(); 

[1,3,4,3,4,3,2,3,3,3,3,3]

trở lại 3

Answer 1

này là khá dễ dàng để thực hiện bản thân:

public static <T> T mostCommon(List<T> list) { 
    Map<T, Integer> map = new HashMap<>(); 

    for (T t : list) { 
     Integer val = map.get(t); 
     map.put(t, val == null ? 1 : val + 1); 
    } 

    Entry<T, Integer> max = null; 

    for (Entry<T, Integer> e : map.entrySet()) { 
     if (max == null || e.getValue() > max.getValue()) 
      max = e; 
    } 

    return max.getKey(); 
} 

---

List<Integer> list = Arrays.asList(1,3,4,3,4,3,2,3,3,3,3,3); 
System.out.println(mostCommon(list)); 

 
3 

Nếu bạn muốn xử lý các trường hợp có nhiều phần tử thường xuyên nhất, bạn có thể quét danh sách một lần để xác định số lần phần tử thường gặp nhất xảy ra, sau đó quét lại danh sách, đặt các phần tử đó trong một bộ và trả lại.

Answer 2

Cách cổ điển để làm điều này là để sắp xếp danh sách và sau đó làm việc qua từng cái một:

public static BigInteger findMostCommon(List<BigInteger> list) { 
    Collections.sort(list); 
    BigInteger mostCommon = null; 
    BigInteger last = null; 
    int mostCount = 0; 
    int lastCount = 0; 
    for (BigInteger x : list) { 
     if (x.equals(last)) { 
      lastCount++; 
     } else if (lastCount > mostCount) { 
      mostCount = lastCount; 
      mostCommon = last; 
     } 
     last = x; 
    } 
    return mostCommon; 
} 

Đây là một chút không gian hiệu quả hơn bằng cách sử dụng băm để kiểm đếm đếm vì nó sắp xếp mảng tại chỗ. Bạn có thể quăng nó vào một lớp generics và thay thế BigInteger bằng T, hoặc chỉ sử dụng Object thay cho BigInteger.

Answer 3

Nếu bạn sẵn sàng để sử dụng Google ổi, bạn có thể sử dụng MultiSet lớp của nó:

MultiSet<BigNumber> numbers = HashMultiSet.create(); 
numberSet.addAll(list); 
Set<MultiSet.Entry<BigNumber>> pairs = numbers.emtrySet(); 
Set<MultiSet.Entry<BigNumber>> copies = new HashSet<MultiSet.Entry<BigNumber>>(pairs); 

Bây giờ, sắp xếp copies bởi giá trị của nó giảm dần.

Answer 4

lẽ là giải pháp đơn giản nhất với ổi trông giống như

Multiset<BigDecimal> multiset = HashMultiset.create(listOfNumbers); 
BigDecimal maxElement = null; 
int maxCount = 0; 
for (Multiset.Entry<BigDecimal> entry : multiset.entrySet()) { 
    if (entry.getCount() > maxCount) { 
    maxElement = entry.getElement(); 
    maxCount = entry.getCount(); 
    } 
} 

Đó là một giải pháp hoàn chỉnh, và ngắn hơn so với các lựa chọn thay thế khác tôi thấy thảo luận.

Answer 5

Ổi cung cấp method sẽ giúp ích, mặc dù nó kém hiệu quả hơn giải pháp của Louis.

BigDecimal mostCommon = 
    Multisets.copyHighestCountFirst(ImmutableMultiset.copyOf(listOfNumbers)) 
     .iterator().next(); 

Answer 6

Dưới đây là một phần mở rộng của Louis' câu trả lời mà hỗ trợ các trường hợp có nhiều yếu tố với cùng xảy ra max đếm:

private <T> List<T> getMostFrequentElements(List<T> list) { 
    Multiset<T> multiset = HashMultiset.create(list); 

    List<T> mostFrequents = new ArrayList<>(); 
    int maxCount = 0; 

    for (Multiset.Entry<T> entry : multiset.entrySet()) { 
     if (entry.getCount() > maxCount) { 
      maxCount = entry.getCount(); 
      mostFrequents.clear(); 
      mostFrequents.add(entry.getElement()); 
     } else if (entry.getCount() == maxCount) { 
      mostFrequents.add(entry.getElement()); 
     } 
    } 

    return mostFrequents; 
} 

Answer 7

Đây là một tinh khiết Java 8 giải pháp (lưu ý: việc phải làm không sử dụng cái này, xem bên dưới):

List<Integer> theList = Arrays.asList(1, 3, 4, 3, 4, 3, 2, 3, 3, 3, 3, 3); 
Integer maxOccurredElement = theList.stream() 
     .reduce(BinaryOperator.maxBy((o1, o2) -> Collections.frequency(theList, o1) - 
         Collections.frequency(theList, o2))).orElse(null); 
System.out.println(maxOccurredElement); 

Một giải pháp khác, bằng cách thu thập các yếu tố theo bản đồ theo tần suất của chúng, sau đó tìm mục nhập giá trị max thứ và trở về chính mình (về cơ bản cùng một giải pháp trên arshajii's answer, viết bằng Java 8):

Integer maxVal = theList.stream() 
       .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 
       .entrySet().stream().max((o1, o2) -> o1.getValue().compareTo(o2.getValue())) 
       .map(Map.Entry::getKey).orElse(null); 

Cập nhật: Nếu các yếu tố thường xuyên nhất là nhiều hơn một, và bạn muốn có được tất cả trong số họ trong một bộ sưu tập, tôi đề xuất hai phương pháp:

Phương pháp A: Sau khi thu thập bộ sưu tập gốc thành số của chúng, lấy giá trị tối đa và lọc các mục nhập bản đồ với giá trị bằng giá trị tối đa này (nếu) chúng tôi tìm thấy. Một cái gì đó như thế này:

Map<Integer, Long> elementCountMap = theList.stream() 
     .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 
List<Integer> result = elementCountMap.values().stream() 
     .max(Long::compareTo).map(maxValue -> elementCountMap.entrySet().stream() 
      .filter(entry -> maxValue.equals(entry.getValue())).map(Map.Entry::getKey).collect(Collectors.toList())) 
     .orElse(Collections.emptyList()); 

Phương pháp B: Sau khi thu thập các bộ sưu tập ban đầu cho một bản đồ với các phím như các yếu tố và giá trị như số họ lần xuất hiện, chuyển bản đồ này thành một bản đồ mới với các phím như số lần xuất hiện, các giá trị dưới dạng danh sách các phần tử với số lần xuất hiện này. Và sau đó tìm phần tử tối đa của bản đồ này với bộ so sánh tùy chỉnh so sánh các khóa và nhận giá trị của mục nhập này. Như thế này:

List<Integer> result = theList.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 
    .entrySet().stream() 
    .collect(Collectors.groupingBy(Map.Entry::getValue, Collectors.mapping(Map.Entry::getKey, Collectors.toList()))) 
    .entrySet().stream().max((o1, o2) -> o1.getKey().compareTo(o2.getKey())).map(Map.Entry::getValue) 
    .orElse(Collections.emptyList()); 

Answer 8

In statistics, this is called the "mode". Một giải pháp vani Java 8 trông như thế này:

Stream.of(1, 3, 4, 3, 4, 3, 2, 3, 3, 3, 3, 3) 
     .collect(Collectors.groupingBy(Functions.identity(), Collectors.counting())) 
     .entrySet() 
     .stream() 
     .max(Comparator.comparing(Entry::getValue)) 
     .ifPresent(System.out::println); 

nào mang lại:

3=8 

jOOλ là một thư viện hỗ trợ mode() trên suối. Các chương trình sau đây:

System.out.println(
    Seq.of(1, 3, 4, 3, 4, 3, 2, 3, 3, 3, 3, 3) 
     .mode() 
); 

Sản lượng:

Optional[3] 

Để đơn giản, tôi bỏ qua sử dụng BigDecimal. Tuy nhiên, giải pháp sẽ giống nhau.

(từ chối trách nhiệm: Tôi làm việc cho công ty đằng sau jOOλ)

Answer 9

Chúng tôi có thể làm chỉ trong một lần lặp một cách dễ dàng:

public static Integer mostFrequent(List<Integer> list) { 

    if (list == null || list.isEmpty()) 
     return null; 

    Map<Integer, Integer> counterMap = new HashMap<Integer, Integer>(); 
    Integer maxValue = 0; 
    Integer mostFrequentValue = null; 

    for(Integer valueAsKey : list) { 
     Integer counter = counterMap.get(valueAsKey); 
     counterMap.put(valueAsKey, counter == null ? 1 : counter + 1); 
     counter = counterMap.get(valueAsKey); 
     if (counter > maxValue) { 
      maxValue = counter; 
      mostFrequentValue = valueAsKey; 
     } 
    } 
    return mostFrequentValue; 
}