如何用分治法（Divide and Conquer）找出数组中重复次数最多的数？

Hey there! I see you already have a working solution to find the most frequent element in your array, but you want to reimplement it using divide and conquer. Let's break this down step by step.

The key here is to split the problem into smaller subproblems, solve each one recursively, then combine the results:

1. Split the array into left and right halves.
2. Recursively find the most frequent element in each half.
3. Compare the two candidate elements from the halves: count how many times each appears in the entire current array segment, then return the one with the higher count.

Function findMostFrequent(arr, left, right):
    // Base case: single element in the segment
    if left == right:
        return arr[left]
    
    // Split the array into two halves
    mid = (left + right) // 2
    leftMost = findMostFrequent(arr, left, mid)
    rightMost = findMostFrequent(arr, mid + 1, right)
    
    // If both halves have the same most frequent element, return it
    if leftMost == rightMost:
        return leftMost
    
    // Count occurrences of both candidates in the full segment
    leftCount = countOccurrences(arr, left, right, leftMost)
    rightCount = countOccurrences(arr, left, right, rightMost)
    
    // Return the element with higher count
    return leftMost if leftCount > rightCount else rightMost

Function countOccurrences(arr, left, right, target):
    count = 0
    for i from left to right:
        if arr[i] == target:
            count += 1
    return count

Here's a complete, tested Java version that works with your sample array:

import java.util.Arrays;

public class MostFrequentElementDivideConquer {

    public static void main(String[] args) {
        int[] repetitive = {5, 12, 5, 17, 5, 5, 5, 39};
        int mostFrequent = findMostFrequent(repetitive, 0, repetitive.length - 1);
        System.out.println("重复次数最多的数是: " + mostFrequent);
    }

    private static int findMostFrequent(int[] arr, int left, int right) {
        // Base case: only one element in the current segment
        if (left == right) {
            return arr[left];
        }

        // Split into left and right subsegments (avoid integer overflow with this mid calculation)
        int mid = left + (right - left) / 2;
        int leftMost = findMostFrequent(arr, left, mid);
        int rightMost = findMostFrequent(arr, mid + 1, right);

        // If both subsegments have the same most frequent element, no need to count
        if (leftMost == rightMost) {
            return leftMost;
        }

        // Count how many times each candidate appears in the full segment
        int leftCount = countOccurrences(arr, left, right, leftMost);
        int rightCount = countOccurrences(arr, left, right, rightMost);

        // Return the element with the higher count
        return leftCount > rightCount ? leftMost : rightMost;
    }

    private static int countOccurrences(int[] arr, int left, int right, int target) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (arr[i] == target) {
                count++;
            }
        }
        return count;
    }
}

• Time Complexity: This approach runs in O(n log n) time. Each recursive split creates two subproblems, and each level of recursion requires O(n) time to count occurrences. This is similar to your original sorted-array approach, but divide and conquer scales better for distributed or parallel processing (you could run left and right subproblem computations in parallel).
• Edge Cases: If multiple elements have the same maximum frequency, this code will return whichever candidate (left or right) has a higher count. If counts are equal, it returns the right candidate—you can adjust this logic if you need to prioritize the first occurrence or another rule.
• Fix for Your Original Code: I noticed a small typo in your existing code: repetative should be repetitive. Also, the logic has some redundant checks; the divide and conquer approach is more modular and easier to maintain.

内容的提问来源于stack exchange，提问作者john tame