归并排序实现数组排序及重复值单次显示问题求助

嗨，我明白你的困扰——当输入多个重复元素时，程序反复输出同一个重复提示，这确实有点烦人。问题出在你当前的逻辑里，每次检测到重复就直接输出，而没有记录哪些重复值已经提示过了。下面给你两种简单的解决思路：

方法1：排序完成后统一处理重复值（推荐） #

这种方法更清晰，把排序和重复值检测的职责分开，逻辑更易维护。核心思路是：

• 先完成归并排序，得到有序数组
• 遍历有序数组，用变量记录上一个元素，仅当当前元素和上一个相同且是第一次遇到该重复值时，输出提示

修改后的主方法示例：

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 假设这里已经完成数组输入和归并排序，得到排序后的sortedArr
    int[] sortedArr = ...; // 替换为你的归并排序结果数组

    if (sortedArr.length < 2) {
        System.out.println("没有重复值");
        scanner.close();
        return;
    }

    Integer lastReportedDuplicate = null;
    for (int i = 1; i < sortedArr.length; i++) {
        if (sortedArr[i] == sortedArr[i-1]) {
            // 仅当该重复值未被输出过时，才打印提示
            if (lastReportedDuplicate == null || sortedArr[i] != lastReportedDuplicate) {
                System.out.println("duplicate: " + sortedArr[i]);
                lastReportedDuplicate = sortedArr[i];
            }
        }
    }
    scanner.close();
}

方法2：在归并过程中跟踪已输出的重复值 #

如果你想在排序过程中同步处理重复值，可以用Set集合来存储已经输出过的重复值，每次检测到重复时先检查集合，未存在则输出并加入集合。

比如修改归并的核心方法：

static void merge(int[] arr, int left, int mid, int right, Set<Integer> reportedDuplicates) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1];
    int[] R = new int[n2];

    System.arraycopy(arr, left, L, 0, n1);
    System.arraycopy(arr, mid + 1, R, 0, n2);

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            // 检测左侧当前元素与下一个元素是否重复（仅在归并时处理相邻重复）
            if (i < n1 - 1 && L[i] == L[i+1] && !reportedDuplicates.contains(L[i])) {
                System.out.println("duplicate: " + L[i]);
                reportedDuplicates.add(L[i]);
            }
            i++;
        } else {
            arr[k] = R[j];
            // 检测右侧当前元素与下一个元素是否重复
            if (j < n2 - 1 && R[j] == R[j+1] && !reportedDuplicates.contains(R[j])) {
                System.out.println("duplicate: " + R[j]);
                reportedDuplicates.add(R[j]);
            }
            j++;
        }
        k++;
    }

    // 处理剩余元素的重复检测
    while (i < n1) {
        arr[k] = L[i];
        if (i < n1 - 1 && L[i] == L[i+1] && !reportedDuplicates.contains(L[i])) {
            System.out.println("duplicate: " + L[i]);
            reportedDuplicates.add(L[i]);
        }
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        if (j < n2 - 1 && R[j] == R[j+1] && !reportedDuplicates.contains(R[j])) {
            System.out.println("duplicate: " + R[j]);
            reportedDuplicates.add(R[j]);
        }
        j++;
        k++;
    }
}

// 对应的归并排序入口方法
static void mergeSort(int[] arr, int left, int right, Set<Integer> reportedDuplicates) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid, reportedDuplicates);
        mergeSort(arr, mid + 1, right, reportedDuplicates);
        merge(arr, left, mid, right, reportedDuplicates);
    }
}

然后在主方法中初始化集合并调用：

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    // 假设这里完成数组输入，得到arr
    int[] arr = ...;
    Set<Integer> reportedDuplicates = new HashSet<>();
    mergeSort(arr, 0, arr.length - 1, reportedDuplicates);
    scanner.close();
}

两种方法里，第一种更推荐，因为逻辑分离更清晰，代码也更容易调试维护。

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