使用线性搜索在两个 ArrayList 中查找元素_技术教程

中查找元素"> 中查找元素" />

本文介绍了如何在 Java 中使用线性搜索算法比较两个字符串类型的 ArrayList，以判断一个列表（例如购物清单）中的所有元素是否都存在于另一个列表（例如食品储藏室清单）中。我们将探讨如何通过循环遍历和条件判断来实现此功能，并提供使用 HashSet 优化搜索效率的替代方案。

线性搜索实现

线性搜索是一种简单的搜索算法，它通过逐个比较列表中的元素与目标值来查找目标值。在我们的场景中，目标是检查 input 列表中的每个元素是否存在于 pantry 列表中。

以下是一个改进后的 linearSearch 方法的示例：

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

public class TheList {

    public static String linearSearch(ArrayList pantry, ArrayList input) {
        for (String ingredient : input) {
            boolean found = false;
            for (String pantryItem : pantry) {
                if (ingredient.equals(pantryItem)) {
                    found = true;
                    break; // 如果找到，跳出内层循环
                }
            }
            if (!found) {
                return "You still need " + ingredient + "!";
            }
        }
        return "You got everything you need!";
    }

    public static void main(String[] args) {
        // 创建食品储藏室列表
        ArrayList pantry = new ArrayList<>();
        pantry.add("Bread");
        pantry.add("Peanut Butter");
        pantry.add("Chips");
        pantry.add("Jelly");

        // 创建用户输入列表
        ArrayList input = inputIngredients();

        // 执行搜索并打印结果
        System.out.println(linearSearch(pantry, input));
    }

    private static ArrayList inputIngredients() {
        Scanner ingredientScan = new Scanner(System.in);
        ArrayList ingredients = new ArrayList<>();

        System.out.println("Enter ingredients (type 'done' to finish):");
        String ingredient;
        while (true) {
            System.out.print("Ingredient: ");
            ingredient = ingredientScan.nextLine();
            if (ingredient.equalsIgnoreCase("done")) {
                break;
            }
            ingredients.add(ingredient);
            System.out.println(ingredient + " added.");
        }
        ingredientScan.close();
        return ingredients;
    }
}

代码解释：

linearSearch 方法：
- 循环遍历 input 列表中的每个 ingredient。
- 对于每个 ingredient，循环遍历 pantry 列表，检查是否存在匹配项。
- 如果找到匹配项，将 found 标记设置为 true，并跳出内层循环。
- 如果内层循环结束后 found 仍然为 false，则表示 ingredient 不在 pantry 中，返回相应的消息。
- 如果所有 ingredient 都在 pantry 中找到，返回 "You got everything you need!"。
main 方法：
- 创建并初始化 pantry 列表。
- 调用 inputIngredients() 方法获取用户输入的 input 列表。
- 调用 linearSearch 方法进行搜索，并打印结果。
inputIngredients 方法：
- 使用 Scanner 类获取用户输入。
- 循环提示用户输入食材，直到用户输入 "done"。
- 将用户输入的食材添加到 ingredients 列表中。
- 返回包含用户输入食材的 ingredients 列表。

运行示例：

Enter ingredients (type 'done' to finish):
Ingredient: Bread
Bread added.
Ingredient: Peanut Butter
Peanut Butter added.
Ingredient: done
You got everything you need!

或者

Enter ingredients (type 'done' to finish):
Ingredient: Bread
Bread added.
Ingredient: Milk
Milk added.
Ingredient: done
You still need Milk!

使用 HashSet 优化搜索

对于大型列表，线性搜索的效率较低，时间复杂度为 O(n*m)，其中 n 和 m 分别是两个列表的长度。可以使用 HashSet 来优化搜索过程。HashSet 允许以接近恒定的时间复杂度 O(1) 查找元素。

以下是使用 HashSet 优化的代码示例：

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

public class TheList {

    public static String search(Set pantry, ArrayList ingredients) {
        for (String ingredient : ingredients) {
            if (!pantry.contains(ingredient)) {
                return "You still need " + ingredient + "!";
            }
        }
        return "Everything is available";
    }

    public static void main(String[] args) {
        // 创建食品储藏室集合
        Set pantry = new HashSet<>();
        pantry.add("Bread");
        pantry.add("Peanut Butter");
        pantry.add("Chips");
        pantry.add("Jelly");

        // 创建用户输入列表
        ArrayList ingredients = inputIngredients();

        // 执行搜索并打印结果
        System.out.println(search(pantry, ingredients));
    }

    private static ArrayList inputIngredients() {
        Scanner ingredientScan = new Scanner(System.in);
        ArrayList ingredients = new ArrayList<>();

        System.out.println("Enter ingredients (type 'done' to finish):");
        String ingredient;
        while (true) {
            System.out.print("Ingredient: ");
            ingredient = ingredientScan.nextLine();
            if (ingredient.equalsIgnoreCase("done")) {
                break;
            }
            ingredients.add(ingredient);
            System.out.println(ingredient + " added.");
        }
        ingredientScan.close();
        return ingredients;
    }
}

代码解释：

search 方法：
- 循环遍历 ingredients 列表中的每个 ingredient。
- 使用 pantry.contains(ingredient) 方法检查 ingredient 是否存在于 pantry 集合中。
- 如果 ingredient 不存在于 pantry 中，返回相应的消息。
- 如果所有 ingredient 都在 pantry 中找到，返回 "Everything is available"。
main 方法：
- 创建并初始化 pantry 集合。
- 调用 inputIngredients() 方法获取用户输入的 ingredients 列表。
- 调用 search 方法进行搜索，并打印结果。
inputIngredients 方法：
- 与线性搜索示例相同。