Java中如何替换嵌套列表的列并实现二分查找？

问题描述 #

我有一个存储字符串的List<List<String>>，需要对其中某一列进行排序（使整个嵌套列表按该列的顺序重新排列），之后通过二分查找在该列中定位元素，找到后输出对应行的全部信息。

示例：对第3列（从1开始计数，对应代码索引为2）排序并查找"345"：
排序前的嵌套列表：

"Test0" "ABC" "123" "A1"
"Test3" "JKL" "901" "A4"
"Test1" "DEF" "345" "A2"        
"Test4" "MNO" "234" "A5"
"Test2" "GHI" "678" "A3"

排序后的嵌套列表：

"Test0" "ABC" "123" "A1"
"Test4" "MNO" "234" "A5"
"Test1" "DEF" "345" "A2"   
"Test2" "GHI" "678" "A3"
"Test3" "JKL" "901" "A4"

查找结果输出：

"Test1" "DEF" "345" "A2"  

我已能提取并排序任意列，但不知道如何将排序结果映射回原嵌套列表。尝试了以下方法，返回的仍是原列表：

public static List<List<String>> replaceCol(String[][] dataArray, List<String> col, int valType) {
    List<List<String>> updatedList = new ArrayList<>();

    for (int i = 0; i < dataArray.length; i++) {
        // 空的内层循环，无意义
        for (int j = 0; j < dataArray.length; j++) {

        }
        // 判断逻辑错误：排序后的列元素与原数组对应位置元素大概率不相等，替换逻辑不会执行
        if (dataArray[i][valType].equalsIgnoreCase(col.get(i))) {
            dataArray[i][valType] = col.get(i);
        }
    }
    updatedList = TwoDArrayToList(dataArray);

    return updatedList;
}

问题分析 #

你的思路存在两个核心错误：

1. 误解排序需求：你需要的是整个嵌套列表按指定列排序（行的顺序随列排序重新排列），而非单独替换原列元素——单独替换会破坏行数据的对应关系，完全不符合示例效果。
2. 现有方法逻辑失效：
   • 内层循环为空，无任何作用；
   • 判断条件dataArray[i][valType].equalsIgnoreCase(col.get(i))不合理：排序后的列是原列排序结果，其第i个元素和原数组第i行对应列元素几乎不会相等，因此替换逻辑从未执行，最终返回原列表。

解决方案 #

正确做法是直接对List<List<String>>按指定列排序，无需单独提取列再替换。排序完成后即可基于该列进行二分查找。

步骤1：按指定列排序嵌套列表 #

使用Collections.sort()自定义比较器，指定排序的列索引（注意：示例中“第3列”对应代码索引为2）：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ListSortUtil {
    // 对List<List<String>>按指定列排序（列索引从0开始）
    public static void sortByColumn(List<List<String>> dataList, int columnIndex) {
        Collections.sort(dataList, new Comparator<List<String>>() {
            @Override
            public int compare(List<String> row1, List<String> row2) {
                // 按字符串自然顺序排序，如需数字排序可转为Integer后比较
                return row1.get(columnIndex).compareTo(row2.get(columnIndex));
            }
        });
    }
}

步骤2：基于指定列的二分查找 #

排序完成后，实现二分查找方法定位目标元素对应的行：

// 二分查找指定列中目标元素对应的行
public static List<String> binarySearchByColumn(List<List<String>> sortedData, int columnIndex, String target) {
    int left = 0;
    int right = sortedData.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        List<String> midRow = sortedData.get(mid);
        String midValue = midRow.get(columnIndex);
        int compareResult = midValue.compareTo(target);

        if (compareResult == 0) {
            return midRow; // 找到目标，返回整行
        } else if (compareResult < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return null; // 未找到目标
}

步骤3：完整测试示例 #

public static void main(String[] args) {
    // 初始化示例数据
    List<List<String>> dataList = new ArrayList<>();
    dataList.add(List.of("Test0", "ABC", "123", "A1"));
    dataList.add(List.of("Test3", "JKL", "901", "A4"));
    dataList.add(List.of("Test1", "DEF", "345", "A2"));
    dataList.add(List.of("Test4", "MNO", "234", "A5"));
    dataList.add(List.of("Test2", "GHI", "678", "A3"));

    // 按第3列（索引2）排序
    int targetColumn = 2;
    sortByColumn(dataList, targetColumn);

    // 二分查找目标元素"345"
    String target = "345";
    List<String> resultRow = binarySearchByColumn(dataList, targetColumn, target);

    // 输出结果
    if (resultRow != null) {
        System.out.println(String.join(" ", resultRow));
    } else {
        System.out.println("未找到目标元素");
    }
}

输出结果 #

Test0 ABC 123 A1
Test4 MNO 234 A5
Test1 DEF 345 A2
Test2 GHI 678 A3
Test3 JKL 901 A4
Test1 DEF 345 A2

补充说明 #

• 如果需要按数字排序（比如示例中的列是数字字符串），可修改比较器逻辑：

  return Integer.parseInt(row1.get(columnIndex)) - Integer.parseInt(row2.get(columnIndex));
  

• 不推荐先提取列排序再映射回原列表的做法，效率更低且逻辑复杂，直接排序整个列表是最优解。

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