Remove Duplicates from Sorted Array II

Problem

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

---

Idea

The idea is the same as Remove Duplicates from Sorted Array. We just use one parameter to record how many duplicates have happen.

---

Solution

Median of Two Sorted Arrays

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

---

Idea1

• If m+n is old (奇数), the median is the number located in position (m+n)/2 of the array (A+B)
• If m+n is even (偶数), the median is the average of element in (m+n)/2 -1 and element in (m+n)/2
• So you need to judge if the m+n is old or even. Then, The problem is find the kth biggest element in array(A+B).
• After you decide the old and even of m+n, the idea of solution is to find the kth element in the array (A+B).

---

Idea2

• The idea is like Merge operation in CLRS. Retrieve the minimal element in A[] and B[] until you reach the median (Maybe two numbers for even case). Complexity is O(m+n)
• We need to carefully treat the cases when A[] is empty or B[] is empty at the beginning
• Use two parameter "front" , "rear" to record two elements for even case. And "rear" for old case.
• During the procedure to find the minimal element in A[]+B[]. You may meet the following cases
• Either A[] or B[] become empty, we just use the other sequence
• If A[] and B[] are non-empty, we will choose the smaller one.

---

Solution

This solution is for Idea2:

Remove Duplicates from Sorted Array

Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

---

Idea

• Index always point to the last element without duplicates
• Use another index traverse the array from 1

---

Solution

---

Search in Rotated Sorted Array

Problem

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

---

Ideas

• http://www.cnblogs.com/TenosDoIt/p/3465240.html

这个思路关注于搜索rotated的subarray. 思路是使用二分查找：在常规情况下，当target > A[mid]时， 应该开始查找数组的后半段，即left = mid+1; 当target < A[mid]时，应该查找数组的前半段，即right = mid-1; 而此题中，当target > A[mid]时，也可能搜索数组的前半段，如：7 8 1 2 3 4 5 （target：8）当target < A[mid]时，也可能搜索数组的后半段，如： 4 5 6 7 8 1 2 （target:2)。下面来分类讨论这两种特殊情况出现的条件。 这两种情况中target都在rotated的数组中。

• target < A[mid]时，搜索后半段必须同时满足以下条件
• A[left] > A[right]          // 表明搜索的边界落在rotated subarray
• target <= A[right]          // target 可能在unrotated的数组的前半部分
• A[right] < A[mid]          // A[mid]在unrotated数组的后半部分,换言之,rotate的点靠近left
我们可以根据上述条件还原rotated前的数组 ... target... A[right].... Middle.... A[mid], 仔细看其实条件就是 A[left] > A[right] (rotated) && target <= A[right] < A[mid]
• target > A[mid]时，搜索前半段
• A[left] > A[right]          // 表明搜索的边界落在rotated subarray
• target > A[right]          // 表明target在unrotated数组的后半部分
• A[mid] < A[right]          // 表明A[mid]在unrotated数组的前半部分，换言之，rotate的点靠近right
unrotated的数组应该是 ... A[mid].... Middle....A[right]....target.....

---

Solution

Another easy idea to understand. This method only focus on searching the unsorted subarray.

---

Special Cases

---

Remove Duplicates from Sorted List II

Problem

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

---

Idea

• Add a dummy node before head
• We operate on Node "head"
• head and head->next is always pointing the node without any duplicates.

---

Note

Data Structure Definition

---

Solution

---

Special Cases

• {1,1}
• {1,1,1}
• {1,1,2,2}

---

Remove Duplicates from Sorted List

Prbolem

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3

---

Ideas

Use nested loops to solve the problem. One loop is used to find the different node.

---

Note

Data Structure Definition

• Don't use delete to remove useless node.
• Don't define two pointer for current node and next node because it's difficult to handle the last node.

---

Solution

---

Special Case

• {1,1}
• {1,1,1}
• {1}

Test KVM performance by "perf"

In last several month, I tried to find an internship opportunity. After submitting 30+ resume, I just receive 2 replies. None of them are willing to hire me. Maybe, I am still too weak and too fool. I will keep moving on -_-!.

---

---

I use the following command to test KVM performance.