遍历HashMap求最小值并排除已选点的代码修复咨询

我看了你的代码，程序卡在第一个最小值无法继续的核心问题有两个：existsX函数逻辑完全颠倒，以及每次寻找最小值时没有排除已处理的point，另外还有列表初始化的小问题。下面我一步步给你拆解修复：

1. 修复existsX函数的逻辑错误 #

你现在的existsX函数逻辑完全反了：它会在dataPoints里只要有一个元素不等于xMin就返回false，只有当所有元素都是xMin时才返回true。但你实际需要的是判断xMin是否已经存在于dataPoints中，正确的写法应该是：

private boolean existsX(List<Integer> dataPoints, int xMin) {
    for (int k = 0; k < dataPoints.size(); k++) {
        if (dataPoints.get(k) == xMin) {
            // 找到匹配的元素，说明已存在
            return true;
        }
    }
    // 遍历完都没找到，说明不存在
    return false;
}

或者用Java 8+更简洁的写法：

private boolean existsX(List<Integer> dataPoints, int xMin) {
    return dataPoints.contains(xMin);
}

2. 寻找最小值时排除已处理的point #

你原来的代码每次都会找全局最小的value对应的point，但如果这个point已经被加入dataPoints了，就会跳过处理，导致循环一直重复获取同一个已处理的xMin，最终卡死。所以需要修改逻辑，在找最小值前先筛选出未处理的point：

假设E是HashMap<Integer, Integer>（key是point，value是对应的值），我们可以新增一个方法，专门获取未处理point中的最小value对应的point：

// 新增方法：获取未处理point中的最小value对应的point
private int getUnprocessedMinPoint(HashMap<Integer, Integer> E, List<Integer> dataPoints) {
    int minValue = Integer.MAX_VALUE;
    int minPoint = -1;
    for (Map.Entry<Integer, Integer> entry : E.entrySet()) {
        int point = entry.getKey();
        int value = entry.getValue();
        // 只考虑未被处理的point
        if (!dataPoints.contains(point) && value < minValue) {
            minValue = value;
            minPoint = point;
        }
    }
    return minPoint;
}

这样每次拿到的xMin都是未被处理过的最小value对应的point，不会重复处理。

3. 调整列表l的初始化位置 #

你现在把l的初始化放在循环外面，会导致每次处理新的xMin时，l会累积之前的点。应该把它移到while循环内部，每次处理新的xMin时创建一个新的列表：

while(dataPoints.size() < E.size()) { // 改成小于更直观，避免相等时的边界问题
    int xMin = getUnprocessedMinPoint(E, dataPoints);
    System.out.println("Xmin "+xMin);
    
    if (!existsX(dataPoints, xMin)) {
        dataPoints.add(xMin);
        List<Integer> l = new ArrayList<>(); // 移到内部，每次新建列表
        // 提取矩阵中对应的值，收集符合条件的j
        for (int j = 0; j < S.getRow(xMin).length; j++) {
            if (S.getEntry(xMin, j) > beta) {
                l.add(j);
                dataPoints.add(j);
            }
        }
        // 将xMin和对应的点存入clusters
        clusters.put(xMin, l);
    }
}

4. 循环条件优化 #

原来的while(E.size()!=dataPoints.size())可以改成while(dataPoints.size() < E.size())，逻辑更清晰，也能避免某些边界情况下的死循环（比如dataPoints意外超过E.size()的情况）。

完整修复后的代码示例 #

整合上面的修改，完整代码大概是这样：

List<Integer> dataPoints = new ArrayList<>(); // 存储已处理的point（包括xMin）
HashMap<Integer, List<Integer>> clusters = new HashMap<>(); // 存储xMin对应的点列表

while(dataPoints.size() < E.size()) {
    int xMin = getUnprocessedMinPoint(E, dataPoints);
    System.out.println("Xmin "+xMin);
    
    if (!existsX(dataPoints, xMin)) {
        dataPoints.add(xMin);
        List<Integer> l = new ArrayList<>();
        // 从矩阵提取对应值，收集符合条件的j
        for (int j = 0; j < S.getRow(xMin).length; j++) {
            if (S.getEntry(xMin, j) > beta) {
                l.add(j);
                dataPoints.add(j);
            }
        }
        clusters.put(xMin, l);
    }
}

// 修复后的existsX函数
private boolean existsX(List<Integer> dataPoints, int xMin) {
    return dataPoints.contains(xMin);
}

// 新增的获取未处理最小point的方法
private int getUnprocessedMinPoint(HashMap<Integer, Integer> E, List<Integer> dataPoints) {
    int minValue = Integer.MAX_VALUE;
    int minPoint = -1;
    for (Map.Entry<Integer, Integer> entry : E.entrySet()) {
        int point = entry.getKey();
        int value = entry.getValue();
        if (!dataPoints.contains(point) && value < minValue) {
            minValue = value;
            minPoint = point;
        }
    }
    return minPoint;
}

这样修改后，程序会依次处理所有未被处理的point，每次找到当前未处理的最小value对应的xMin，提取矩阵中符合条件的点，存入clusters，同时标记这些点为已处理，不会再重复处理。

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