中查找元素” />
本文介绍了如何在 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<String> pantry, ArrayList<String> 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<String> pantry = new ArrayList<>(); pantry.add("Bread"); pantry.add("Peanut Butter"); pantry.add("Chips"); pantry.add("Jelly"); // 创建用户输入列表 ArrayList<String> input = inputIngredients(); // 执行搜索并打印结果 System.out.println(linearSearch(pantry, input)); } private static ArrayList<String> inputIngredients() { Scanner ingredientScan = new Scanner(System.in); ArrayList<String> 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<String> pantry, ArrayList<String> 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<String> pantry = new HashSet<>(); pantry.add("Bread"); pantry.add("Peanut Butter"); pantry.add("Chips"); pantry.add("Jelly"); // 创建用户输入列表 ArrayList<String> ingredients = inputIngredients(); // 执行搜索并打印结果 System.out.println(search(pantry, ingredients)); } private static ArrayList<String> inputIngredients() { Scanner ingredientScan = new Scanner(System.in); ArrayList<String> 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 方法：
- 与线性搜索示例相同。
注意事项：
- HashSet 不保证元素的顺序。如果需要保持元素的顺序，可以使用 LinkedHashSet。
- HashSet 只能存储唯一的元素。如果列表中包含重复的元素，HashSet 只会存储一个副本。
总结
本文介绍了如何使用线性搜索算法和 HashSet 在 Java 中比较两个字符串类型的 ArrayList。线性搜索算法简单易懂，但效率较低。HashSet 可以显著提高搜索效率，特别是在处理大型列表时。选择哪种方法取决于具体的应用场景和性能要求。
评论（已关闭）
评论已关闭