Java 中高效比对两个字符串列表：从线性查找优化到集合操作

import java.util.ArrayList;
import java.util.List;

public class ListComparator {

    /**
     * 使用 ArrayList 进行线性查找，找出在 ingredients 中但不在 pantry 中的物品。
     * 时间复杂度：O(M*N)，其中 M 是 ingredients 列表的大小，N 是 pantry 列表的大小。
     * 因为 pantry.contains() 操作在最坏情况下需要遍历整个 pantry 列表。
     *
     * @param pantry 现有库存列表
     * @param ingredients 用户所需食材列表
     * @return 缺少的食材列表
     */
    public static List<String> findMissingItemsLinearSearch(
            ArrayList<String> pantry, ArrayList<String> ingredients) {
        List<String> missingItems = new ArrayList<>();
        for (String ingredient : ingredients) {
            // 检查 pantry 是否包含当前 ingredient
            if (!pantry.contains(ingredient)) {
                missingItems.add(ingredient);
            }
        }
        return missingItems;
    }

    public static void main(String[] args) {
        ArrayList<String> pantry = new ArrayList<>();
        pantry.add("Bread");
        pantry.add("Peanut Butter");
        pantry.add("Chips");
        pantry.add("Jelly");
        pantry.add("Milk");

        ArrayList<String> shoppingList = new ArrayList<>();
        shoppingList.add("Bread");
        shoppingList.add("Milk");
        shoppingList.add("Eggs"); // 缺少
        shoppingList.add("Butter"); // 缺少

        List<String> missing = findMissingItemsLinearSearch(pantry, shoppingList);

        if (missing.isEmpty()) {
            System.out.println("您拥有所有必需的物品！");
        } else {
            System.out.println("您仍然需要以下物品：");
            for (String item : missing) {
                System.out.println("- " + item);
            }
        }
    }
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SetComparator {

    /**
     * 使用 HashSet 进行高效查找，找出在 ingredients 中但不在 pantry 中的物品。
     * 时间复杂度：O(N + M)，其中 N 是 pantry 列表的大小（转换为 HashSet 的时间），
     * M 是 ingredients 列表的大小（遍历并查找的时间）。
     *
     * @param pantryList 现有库存列表 (ArrayList)
     * @param ingredientsList 用户所需食材列表 (ArrayList)
     * @return 缺少的食材列表
     */
    public static List<String> findMissingItemsOptimized(
            ArrayList<String> pantryList, ArrayList<String> ingredientsList) {

        // 将 pantryList 转换为 HashSet，以便进行 O(1) 平均时间复杂度的查找
        Set<String> pantrySet = new HashSet<>(pantryList);

        List<String> missingItems = new ArrayList<>();
        for (String ingredient : ingredientsList) {
            // 在 HashSet 中查找，平均时间复杂度为 O(1)
            if (!pantrySet.contains(ingredient)) {
                missingItems.add(ingredient);
            }
        }
        return missingItems;
    }

    public static void main(String[] args) {
        ArrayList<String> pantry = new ArrayList<>();
        pantry.add("Bread");
        pantry.add("Peanut Butter");
        pantry.add("Chips");
        pantry.add("Jelly");
        pantry.add("Milk");

        ArrayList<String> shoppingList = new ArrayList<>();
        shoppingList.add("Bread");
        shoppingList.add("Milk");
        shoppingList.add("Eggs"); // 缺少
        shoppingList.add("Butter"); // 缺少

        List<String> missing = findMissingItemsOptimized(pantry, shoppingList);

        if (missing.isEmpty()) {
            System.out.println("您拥有所有必需的物品！");
        } else {
            System.out.println("您仍然需要以下物品：");
            for (String item : missing) {
                System.out.println("- " + item);
            }
        }
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class ShoppingListApp {

    // 预设的库存列表
    private static final ArrayList<String> PANTRY_ITEMS = new ArrayList<>();
    static {
        PANTRY_ITEMS.add("Bread");
        PANTRY_ITEMS.add("Peanut Butter");
        PANTRY_ITEMS.add("Chips");
        PANTRY_ITEMS.add("Jelly");
        PANTRY_ITEMS.add("Milk");
        PANTRY_ITEMS.add("Eggs");
        PANTRY_ITEMS.add("Sugar");
        PANTRY_ITEMS.add("Flour");
    }

    /**
     * 接收用户输入的食材列表。
     *
     * @return 用户输入的食材列表
     */
    private static ArrayList<String> getUserIngredients() {
        ArrayList<String> ingredients = new ArrayList<>();
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入您需要的食材（输入 'done' 结束）：");

        while (true) {
            System.out.print("> ");
            String inputLine = scanner.nextLine().trim(); // 读取一行并去除首尾空格

            if (inputLine.equalsIgnoreCase("done")) { // 不区分大小写判断 'done'
                break;
            }
            if (!inputLine.isEmpty()) { // 避免添加空字符串
                ingredients.add(inputLine);
            }
        }
        // scanner.close(); // 注意：在 main 方法中关闭 Scanner 更合适，或者确保在不再需要时关闭
        return ingredients;
    }

    /**
     * 使用 HashSet 查找缺少的物品。
     *
     * @param pantryList 现有库存列表
     * @param ingredientsList 用户所需食材列表
     * @return 缺少的食材列表
     */
    public static List<String> findMissingItems(
            ArrayList<String> pantryList, ArrayList<String> ingredientsList) {

        Set<String> pantrySet = new HashSet<>(pantryList);
        List<String> missingItems = new ArrayList<>();

        for (String ingredient : ingredientsList) {
            // 为了处理大小写不一致的问题，可以将所有字符串转换为小写再比较
            if (!pantrySet.contains(ingredient.toLowerCase())) {
                missingItems.add(ingredient);
            }
        }
        return missingItems;
    }

    public static void main(String[] args) {
        // 获取用户输入的食材列表
        ArrayList<String> userShoppingList = getUserIngredients();

        // 查找缺少的物品
        List<String> missing = findMissingItems(PANTRY_ITEMS, userShoppingList);

        // 输出结果
        if (missing.isEmpty()) {
            System.out.println("您拥有所有必需的物品！可以开始烹饪了！");
        } else {
            System.out.println("您仍然需要以下物品去超市购买：");
            for (String item : missing) {
                System.out.println("- " + item);
            }
        }
        // 在程序结束时关闭 Scanner
        // 注意：如果 getUserIngredients 内部关闭了 scanner，这里就不能再关闭了
        // 最佳实践是只在 main 方法中创建和关闭一次 Scanner
        // Scanner ingredientScan = new Scanner(System.in);
        // ingredientScan.close();
    }
}