档案日期2014的46

  大多数Java初学者在使用动态数组时，会不假思索的选择ArrayList。但实际上，除了ArrayList，还有LinkedList可供选用。

  那么，在使用Java的动态数组时，怎样在ArrayList与LinkedList之间做出选择呢？

  一言以蔽之，在大多数使用场景中，ArrayList与ArrayDeque要优于LinkedList。对于初学者来说，在拿不准用哪个时，不妨使用ArrayList。

  LinkedList与ArrayList是List接口的两种不同的实现。LinkedList使用双向链表实现。ArrayList则使用动态可变长数组实现。

  对于标准的链表和数组运算，不同的方法会有不同的算法运行时间。

  对于LinkedList<E>：

• get(int index)  O(n)
• add(E element)  O(1)
• add(int index, E ...

题目描述：

Sort a linked list in O(n log n) time using constant space complexity.

题目大意：

使用常数空间复杂度，对一个链表执行O(n log n）时间复杂度的排序

解题思路：

归并排序，链表的中点可以通过“快慢指针”法求得。

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self ...

由于链表（LinkedList）不支持随机访问（Random Access），只允许顺序访问，因此对于链表的O(logn)时间复杂度的排序算法不可以采用诸如快速排序等基于随机访问的排序算法，而归并排序可以满足这一需求。

归并排序是分治法（Divide and Conquer）的典型应用，其伪代码如下：

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

下面的Java代码实现了对单链表（singly linked list）的归并排序，代码实现优美 ...

jQuery UI中提供的Spinner组件可以将input[type=text]文本框转换为一个数字输入框，类似于HTML中新增的input[type=number]，并支持使用键盘上下键以及鼠标滚轮对其中的数值进行更改。

注：鼠标滚轮事件缺省只支持部分浏览器，可使用jQuery Mousewheel插件添加跨浏览器的鼠标滚轮事件支持

jQuery UI Spinner实例如下：

Select a value:

上例代码如下：

<script src="https://libs.baidu.com/jqueryui/1.10.4/jquery-ui.min.css"></script> ...