|
public class ListUtils { public static List<Integer> mergeSortedLists0(@NonNull List<Integer> sortedList1, @NonNull List<Integer> sortedList2) { var resultList = new ArrayList第二种实现方法中的条件分析:(sortedList1.size() + sortedList2.size()); var i = 0; var j = 0; while (i < sortedList1.size() && j < sortedList2.size()) { var elem1 = sortedList1.get(i); var elem2 = sortedList2.get(j); if (elem1 <= elem2) { resultList.add(elem1); ++i; } else { resultList.add(elem2); ++j; } } while (i < sortedList1.size()) { resultList.add(sortedList1.get(i++)); } while (j < sortedList2.size()) { resultList.add(sortedList2.get(j++)); } return resultList; } // more generic implementation: // * not to assume input lists are ArrayLists (use index to get value from a linked list is slow) // * use template to support different kinds of element types in lists public static <T extends Comparable > List<T> mergeSortedLists(@NonNull List<T> sortedList1, @NonNull List<T> sortedList2) { var resultList = new ArrayList<T>(sortedList1.size() + sortedList2.size()); var iter1 = sortedList1.iterator(); var iter2 = sortedList2.iterator(); T elem1 = null; T elem2 = null; while (true) { if (elem1 == null && iter1.hasNext()) { elem1 = iter1.next(); } if (elem2 == null && iter2.hasNext()) { elem2 = iter2.next(); } if (elem1 == null && elem2 == null) { break; } if (elem1 != null && (elem2 == null || elem1.compareTo(elem2) <= 0)) { resultList.add(elem1); elem1 = null; } else { resultList.add(elem2); elem2 = null; } } return resultList; } }
#1: e1 == null && e2 == null: break #2: e1 == null && e2 != null: add e2 #3: e1 != null && e2 == null: add e1 #4: e1 != null && e2 != null && <e1, e2>: add e1 #5: e1 != null && e2 != null && <e2, e1>: add e2在程序中,#1是一个分支;#3和#4是一个分支;其余的(#2和#5)是一个分支。 这个算法的想法很简单,但程序编写起来意外地麻烦,感觉难以编写得简洁明快。第二种方法中之所以判断元素为null与否,主要是因为Java中的Iterator不像C++ STL中的那样把取值和移动分开(分别用*和++操作符),而是合为一体了(next()方法),所以使得该问题的实现有点麻烦。用C++来写的话,就好多了:
template <typename T> std::vector<T> mergeSortedList(std::vector<T>& sortedList1, std::vector<T>& sortedList2) { typename std::vector<T>::iterator iter1 = sortedList1.begin(); typename std::vector<T>::iterator iter2 = sortedList2.begin(); typename std::vector<T> resultList; while (iter1 != sortedList1.end() && iter2 != sortedList2.end()) { if (*iter1 < *iter2) { resultList.push_back(*iter1++); } else { resultList.push_back(*iter2++); } } while (iter1 != sortedList1.end()) { resultList.push_back(*iter1++); } while (iter2 != sortedList2.end()) { resultList.push_back(*iter2++); } return resultList; }第一种实现方法比较简洁,而且它也可以改写成用模板的通用程序,但是如果表是链表,随机存取是很慢的。如果一定要用这种写法,则宁可牺牲一点存储空间,把链表拷贝到ArrayList中再处理,会快得多。
对,并且只储存非零系数。对于这个例子,则只需储存两个结点:{<1, 0>, <2, 10000>}。
多项式加法: 假设有多项式P(n+1个系数)和Q(m+1个系数),而且m<n,那么其和为:P(x, n): {p(0), p(1), p(2), ..., p(n)} P(x, n): {q(0), q(1), q(2), ..., q(m)} m < n R(x, n) = P + Q: {p(0) + q(0), p(1) + q(1), ..., p(m) + q(m), p(m+1), ..., p(n)}显然,其时间为O(n)。 这种普通的多项式适合用顺序存储的表来表示。对于项比较“稀疏”的那种多项式,则适合用链表来表示。其相加的算法为:从两个表的表头开始各取一个元素,比较其指数:把小的那个放入新表。如果两个相等,则将其系数相加,结果不为0的话,放入新表。这跟前面的合并有序表的算法类似。 多项式乘法:可以转换为多个多项式加法。用一个多项式的每一项去乘另一个多项式,就得到一个新的多项式。最后把所有的多项式按上述“稀疏”多项式的要领相加即可。