Java实现去重与随机分配算法

本文主要介绍了Java编程中两个常见的算法问题：去重和随机分配，并给出了相应的解决方案。第一个问题包括两种去重方法，一种是通过额外的List实现，另一种是利用HashMap来实现。第二个问题是随机分配资源，使用了HashMap和Random类来完成。 ### 1. 去重 #### 方法一：额外定义List去重 在给定的代码中，首先创建一个新的ArrayList `tmp` 用于存储未重复的元素。然后，通过迭代原始列表 `arrs`，检查每个元素是否已存在于 `tmp` 中。如果存在，就从 `arrs` 中移除该元素；否则，将其添加到 `tmp`。这种方法简单易懂，但效率较低，因为每次检查都需要遍历整个 `tmp` 列表。 ```java public static void RemoveRepeat(List<Integer> arrs) { List<Integer> tmp = new ArrayList<Integer>(); Iterator<Integer> it = arrs.iterator(); while (it.hasNext()) { int a = it.next(); if (tmp.contains(a)) // 这里会进行一次线性查找 it.remove(); else tmp.add(a); } } ``` #### 方法二：HashMap实现去不重 使用HashMap可以显著提高去重的效率，因为HashMap的查找操作通常具有O(1)的时间复杂度。在这个方法中，遍历输入列表 `arrs`，将每个元素作为键，出现次数作为值存入HashMap `tmp`。再次遍历列表时，如果某个元素在HashMap中的值为1，则从原始列表中移除。 ```java public static void RemoveNotRepeat(List<Character> arrs) { Map<Character, Integer> tmp = new HashMap<>(); for (char c : arrs) { if (tmp.containsKey(c)) tmp.put(c, tmp.get(c) + 1); else tmp.put(c, 1); } Iterator<Character> it = arrs.iterator(); while (it.hasNext()) { Character c = it.next(); if (tmp.get(c) == 1) // 使用HashMap快速判断 it.remove(); } } ``` ### 2. 随机分配 在给定的场景中，需要将一系列票（tickets）随机分配给顾客（customers）。这里使用了HashMap `result` 来存储分配结果，以及Random类生成随机索引来完成分配。代码中通过循环遍历顾客列表，每次都生成一个随机索引，取出对应的顾客和票，并从原列表中移除，以确保不会重复分配。 ```java public static Map<String, String> TicketDispatch(List<String> customers, List<String> tickets) { Map<String, String> result = new HashMap<String, String>(); Random r = new Random(); int iCustomer; int iTicket; for (int i = customers.size(); i > 0; i--) { iCustomer = r.nextInt(i); // 生成[0, i)之间的随机索引 iTicket = r.nextInt(tickets.size()); result.put(customers.get(iCustomer), tickets.get(iTicket)); // 分配并存储结果 customers.remove(iCustomer); // 移除已分配的顾客 tickets.remove(iTicket); // 移除已分配的票 } return result; } ``` ### 3. 递归 虽然在提供的摘要信息中没有给出完整的递归代码，但Java中的递归通常用于解决那些可以通过简化自身规模来解决的问题，如计算阶乘、搜索树结构等。递归函数通常包含基本情况（base case），这是可以直接返回结果的情况，以及递归情况，即将问题分解成更小的部分并调用自身来处理。 例如，一个简单的阶乘函数的递归实现可能如下： ```java public static int factorial(int n) { if (n == 0 || n == 1) { // 基本情况 return 1; } else { // 递归情况 return n * factorial(n - 1); } } ``` 总结来说，上述Java代码展示了在处理数据时常见的两种算法：去重和随机分配，以及递归的基本概念。理解并熟练掌握这些算法对提升Java编程能力至关重要。