Java 集合练习（购物小票 2）

发表于 分类于 阅读次数： 本文字数： 783 阅读时长 ≈ 3 分钟

OOP h12

字符串 content 是一个超市的历次购物小票的合计，每次购物的明细之间用分号分割，每个商品之间用半角逗号分开

请找出哪 n（n >= 1）个商品被同时购买的频率最高，将这 n 个商品名称的集合（set）返回

@param content 历次购物的明细，例如：炸鸡,可乐,啤酒;薯片,啤酒,炸鸡;啤酒,雪碧,炸鸡

@param n

@return 哪 n 个商品被同时购买的频率最高，将这 n 个商品名称的集合（set）返回

不会出现并列的情况

和 h11 类似，只不过从找出两个同时购买的商品改为找出 n 个同时购买的商品。找出两个商品很简单，只需要两层循环遍历。但 n 层循环遍历是不可能的，那么如何才能找出 n 个商品呢？

可以发现，h12 的难点就在于，给出任意数量的商品，如何才能找出其中 n 个商品的所有组合。

为此，需要新建方法 getNItems，来获取 n 个商品。

getNItems

这个问题可以抽象为，从一个列表中取出所有 n 个元素组成的集合的问题。

显然多层循环嵌套不可以解决问题，可以采用分治和递归的思想。

例如，从 5 个元素中取出 3 个元素，等价于从 5 个元素中取出 1 个元素（1），再从剩下的 4 个元素中取出 2 个元素。从 4 个元素中取出 2 个元素，等价于从 4 个元素中取出 1 个元素（2），再从剩下的 3 个元素中取出 1 个元素（3）：

  • （1）需要遍历这 5 个元素，分别对应取出元素 1-5 的情形，每种情况再对应递归从剩下的 4 个元素中取出 2 个元素；
  • 假设（1）取出了元素 1，则（2）需要遍历剩下这 4 个元素，分别对应取出元素 2-5 的情形，每种情况再对应递归从剩下的 3 个元素中取出 1 个元素；
  • 假设（2）取出了元素 2，则（3）只需在剩下的元素 3-5 中取出 1 个元素，取出后直接连同（1）和（2）取出的元素一起存放在结果中，这就对应了从 5 个元素中取出 3 个元素的一种情况。

举个例子之后，事情就变得简单了。目前我们已知包含所有元素的列表（不用数组，因为列表更强），知道要找出多少个元素组成的集合。通过上述例子的分析，我们发现还需要一个列表用于存放每一次取出的元素，以便于和最后一次取出的元素一起作为结果保存。所以方法需要三个参数：剩余元素、取出的元素、尚需取出的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param remainItems 剩余的需要组合的商品列表
 * @param collectItems 已经组合的商品列表
 * @param count 剩余的需要组合的商品数量
 * @return count个商品的集合的集合
 */
public Set<Set<String>> getNItems(List<String> remainItems, List<String> collectItems, int count) {
  int i;
  Set<Set<String>> result = new HashSet<>();// 存放结果
  // 最后一次递归，先看下一部分再看这里
  if (count == 1) {
    for (String remainItem : remainItems) {// 这一次执行只需要取出一个元素，所以只需要遍历剩余元素依次取出即可
      Set<String> collectItemsSet = new HashSet<>(collectItems);// 已经取出的元素，差一个就够n个了
      collectItemsSet.add(remainItem);// 将遍历的这个元素加入到取出元素列表中
      result.add(collectItemsSet);// 完成n个元素的一种组合方式（是一个集合），作为结果（是集合的集合）的一个元素加入其中
    }
    return result;// 返回结果
  }
	// 前若干次递归开始部分
  count--;// 这一次执行可以取出一个元素，所以尚需取出的元素个数减1
  for (i = 0; i < remainItems.size(); i++) {// 遍历剩余未取出的元素，依次取出
    List<String> tempRemainItems = new ArrayList<>(remainItems);// 当前剩余元素
    List<String> tempCollectItems = new ArrayList<>(collectItems);// 当前取出元素
    tempCollectItems.add(tempRemainItems.remove(i));// 从剩余元素中取出其中的第i个元素，把取出的这个元素加入到取出元素列表中
    result.addAll(getNItems(tempRemainItems, tempCollectItems, count));// 递归，从剩余?-1个元素中取n-1个元素，结果加入到result
  }
  return result;// 返回最终结果
}

getFrequentItem

在实现了从若干个商品中取出 n 个商品的所有组合的方法后，问题就和 h11 完全相同了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 字符串content是一个超市的历次购物小票的合计，每次购物的明细之间用分号分割，每个商品之间用半角逗号分开
 * 请找出哪n(n>=1)个商品被同时购买的频率最高，将这n个商品名称的集合（set）返回
 *
 * @param content，历次购物的明细，例如：炸鸡,可乐,啤酒;薯片,啤酒,炸鸡;啤酒,雪碧,炸鸡
 * @param n
 * @return 哪n个商品被同时购买的频率最高，将这n个商品名称的集合（set）返回
 *  不会出现并列的情况
 */
public Set<String> getFrequentItem(String content,int n)  {
  int i, count, max;
  String[] shopping;// 购物数组，每个元素对应一次购物
  List<String> items;// 一次购物的商品列表，每个元素对应一个商品，用列表方便后续操作
  Set<String> nItemsAns;
  Map<Set<String>, Integer> nItemsMap;
  Set<Set<String>> nItemsSet;

  shopping = content.split(";");
  nItemsMap = new HashMap<>();
  for (i = 0; i < shopping.length; i++) {// 遍历所有次购物
    items = Arrays.asList(shopping[i].split(","));// 对于一次购物，得到商品列表
    Set<Set<String>> nItems = new HashSet<>(getNItems(items, new ArrayList<>(), n));// 调用上述方法，得到 所有n商品集合 的集合
    for (Set<String> nItem : nItems) {// 遍历集合的集合
      count = nItemsMap.getOrDefault(nItem, 0);// 对于一个集合，对应n个同时出现商品的一种组合方式，若没出现过则count为1，若出现过则count为出现的次数
      nItemsMap.put(nItem, count + 1);// 对应组合方式（键）出现的次数（值）加1
    }
  }

  max = 0;
  nItemsAns = new HashSet<>(n);
  nItemsSet = nItemsMap.keySet();// 键集合
  for (Set<String> nItem: nItemsSet) {// 遍历键集合
    if (max < nItemsMap.get(nItem)) {// 取键对应的值，若比max大，则进一步操作
      max = nItemsMap.get(nItem);// 更大的值更新max
      nItemsAns = nItem;// 更大的值的键更新最终结果
    }
  }

  return nItemsAns;
}