中查找元素" />
本文介绍了如何在 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 可以显著提高搜索效率，特别是在处理大型列表时。选择哪种方法取决于具体的应用场景和性能要求。
