Return top k values from an array of length N

Best solution: We can use the heap of length k to store the top k values. The smallest value Y is on the top of the heap. When considering a new value X, if X <= Y, we don't need to change the original heap. If X > Y, X should replace Y on the heap and then we need to update the heap again. The update algorithm is O(logK).

The time of this algorithm is O(n*logK).

The definition of the heap: http://en.wikipedia.org/wiki/Heap_(data_structure)

How to update the min-heap:


If N is positive integer, the range is not very big. We can consider use extra space counte[MAXN] to record the frequency of the integer, then pick up the top k frequency numbers.

Finding Maximum/Minimum Value in an Array

Solution 1: If we just travel the whole array, find out the maximum and minimum number.
We need to compare 2*N times to find out the maximum and minimum number.

Solution 2: We put two neighbors in the array into one group, then use Max and Min variable to store the current max and min value. Then, we travel to the next group. If the min value in the next group is smaller than the Min variable and update Min variable. We update Max variable using the same way. We repeat the same process in the whole array.

We need to compare 1.5*N times.

Given a sorted array of integers, how can you find the location of a particular integer x?

Best Solution: Binary Search O(Logn)

Check whether there is a cycle in the linked list(检查链表里是否有环).

Set two pointers(fast, slow) both points the head of the linked list. The slow pointer moves one step, and the fast pointer moves two steps. If there is a cycle, the fast pointer will meet the slow pointer. The program is as follows:



How to find out the entrance of the cycle?

If we found the cycle in the linked list, we let p2 come back to the head of the linked list and go ahead, however, the length of the step should be one. When the meet with P1 and P2, that is the entrance of the cycle.

Chinese Prove:
在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有

p1走的路径： p+c ＝ n； c为p1和p2相交点，距离环路入口的距离

p2走的路径： p+c+k*L = 2*n； L为环路的周长，k是整数

显然，如果从p+c点开始，p1再走n步骤（即k*L步，p1又循环了k圈）的话，还可以回到p+c这个点

同时p2从头开始走的话，经过n步，也会达到p+c这点

显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

From Chinese version: http://blog.csdn.net/sayigood/archive/2009/02/15/3891735.aspx

Copy Complex Node

Given a complex node, one pointer m_pNext points to the next node, and the other pointer m_pSibling points to the random node or NULL in the linked list. How to copy this complex linked list? Function: ComplexNode* Clone(ComplexNode* pHead).




The the first solution: use O(n) space to implement O(n) time performance.
The first step copys every node N of the linked list to a new node N', then connect all of these new nodes together. The trick is to build a haspmap stored into a pair . The second step is to find the corresponding node to copy the m_pSibling node of original linked list. Due to the hashmap, we can use O(1) to find S' from S.

The second solution is to implement O(n) performance without using additional space O(n).

In first step, we still copy a new node N' corresponding to the node N of original linked list. However, we put the N' back to the N as the following graph:





The second step is to copy the m_pSibling node of the original linked list. If the m_pSibling pointer of the node N of the original linked list points to S, then the m_pSibling pointer of the correspoinding node N' points to S' like the following graph.





The last step is to divide this linked list into two separate parts: the odd nodes belong to the original linked list; the even nodes belong to the new linked list.





The whole process is:


From Chinese version: http://zhedahht.blog.163.com/

Given a sorted array A[1..n] with n integers, and an integer t, find all pairs (x,y) of elements in A such that x+y is smaller than t. 2. Can we do

Array A[i...n]. t is the given value.
Create a hash of size t assuming t <= n and 1 < t.
Iterate the array to create a hash O(t) (t < n).
The key of the hash should be the value A[i] and value of the hash should be (t - A[i]).

Iterate again over the array again (which is O(t)).
Look up every key in hash matching the value of A[i]. Check if there is an existing key in the hash table which matches value of the A[i].

The hash lookups are constant time. The overall complexity is 2n.

Given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list.

Solution: move the data from the next node into the current node and then deleting the next node. This solution has O(1) runtime.



只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。

办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。