将多重集表示为链表

Question

多重集与集合相似，除了重复计数。我们想将多重集表示为链表。第一代表想到的是使用 LinkedList<T> ，其中相同的项目可以出现在几个指标。对于 example:the 多重集

{ "Ali Baba" , "Papa Bill", "Marcus", "Ali Baba", "Marcus", "Ali Baba" }

可以表示为链表在索引 0 处具有 "Ali Baba"，在索引 1 处具有 "Papa Bill" 的字符串， "Marcus" 在索引 2，"Ali Baba" 在索引 3，依此类推，总共 6 串。

教授想要将多重集表示为 pair <item,integer>，其中称为项目乘法的整数告诉我们项目在多重集中出现了多少次。这样上面的多重集表示为链表，其中 Pair("Ali Baba" ,3) 在索引 0 处，Pair("Papa Bill", 1) 在索引 1 处，Pair("Marcus",2 ) 在索引 2.

方法是（他写的good luck, how nice >:[ )

public static <T>  LinkedList<Pair<T,Integer>> convert(LinkedList<T> in){

//good luck
}

该方法将第一个表示转换为 Pair 表示。如果 in 为 null，则将 returns 转换为 null。也可以随意修改输入列表。

他给了我们一对 class-

public class Pair<T,S>
{

  // the fields

  private T first;

  private S second;


  // the constructor
  public Pair(T f, S s)
  {

     first = f;
     second = s;
  }

  // the get methods
  public T getFirst()
  {
     return first;
  }

  public S getSecond()
  {
     return second;
  }

// the set methods
  // set first to v
  public void setFirst(T v)
  {
     first = v;
  }

  // set second to v
  public void setSecond(S v)
  {
     second = v;
  }

}

我是编程新手，我一直做得很好，但我什至不知道如何开始这个程序。以前从未做过这样的事情。

Answer 1

您的要求：

您的输入：LinkedList
你的输出：LinkedList>

1 - 编写一个循环来读取您的输入

2 - 以方便的方式处理/存储它：用户地图。实际上，使用保持顺序的linkedhashmap

2bis - 如果您不能使用 Map，请直接对两个数组执行相同的操作：一个 T 数组和一个整数数组。您必须管理插入、搜索和计数。

3 - 迭代你的数组，并创建你的输出

从2开始比较容易，如果行得通，换成2bis

Answer 2

如果允许您使用临时 LinkedList 您可以这样做：

import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {
        LinkedList<String> test = new LinkedList<String>();
        test.add("Ali Baba");
        test.add("Papa Bill");
        test.add("Marcus");
        test.add("Ali Baba");
        test.add("Marcus");
        test.add("Ali Baba");
        LinkedList<Pair<String, Integer>> result = convert(test);
        for(Pair<String, Integer> res : result) {
            System.out.println(res.getFirst() + " :" + res.getSecond());
        }
    }

    public static <T> LinkedList<Pair<T, Integer>> convert(LinkedList<T> in) {
        LinkedList<Pair<T, Integer>> returnList = new LinkedList<>();
        LinkedList<T> tmp = new LinkedList<T>();
        // iterate over your list to count the items
        for(T item : in) {
            // if you already counted the current item, skip it
            if(tmp.contains(item)) {
                continue;
            }
            // counter for the current item
            int counter = 0;

            //iterate again over your list to actually count the item
            for(T item2 : in) {
                if(item.equals(item2)) {
                    counter ++;
                }
            }
            // create your pair for your result list and add it
            returnList.add(new Pair<T, Integer>(item, counter));

            // mark your item as already counted
            tmp.add(item);
        }
        return returnList;
    }
}

这样我就得到了

的期望输出

Ali Baba :3
Papa Bill :1
Marcus :2

将多重集表示为链表

Representing multisets as LinkedLists

java

generics

linked-list

type-conversion