God is in the details. ---Mies van der Rohe

Happy everyday!

2016-03-07
两个已排序数组的第K大元素

两个已排序数组A[m]、B[n]，求两者所有元素的第k大的元素

方法一

直接merge两个数组，然后求第K大的元素

方法二

使用计数器h记录当前已经找到第m大的元素；
使用两个指针pA和pB，分别指向数组A和B；
如果A当前元素小，pA++，m++;
如果B当前元素小，pB++，m++;
当m==k，得到答案。
O(k)时间，O(1)空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private:
	static int find_kth(std::vector<int>::const_iterator A, int m,
						std::vector<int>::const_iterator B, int n,
						int k) {
        int i = 0;
        int j = 0;
        int h = 1;
        
        if (0 == m) return B[k - 1];
        if (0 == n) return A[k - 1];
        if (1 == k) return min(A[0], B[0]);
        
        while (i<m && j<n) {
            if (A[i] <= B[j]) {
                i++;
                h++;
                if (h == k) return A[i - 1];
            } else {
                j++;
                h++;
                if (h == k) return B[j - 1];
            } 
        }
	}

方法三

充分利用有序，每次排除k/2个元素，使用递归
·当A或B为空时，直接返回B[k-1]或A[k-1]
·当k==1时，返回min(A[0], B[0])
·当A[k/2 - 1] == B[k/2 - 1]时，返回A[k/2 - 1]或B[k/2 - 1]
假设A和B的元素个数都大于k/2，
·if (A[k/2 - 1] < B[k/2 - 1]) 排除A数组的k/2个元素。
·else if (A[k/2 - 1] > B[k/2 - 1]) 排除B数组的k/2个元素。
·else 找到了第k大的元素，直接返回A[k/2 - 1]或B[k/2 - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
	double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
		const int m = A.size();
		const int n = B.size();
		int total = m + n;

		if (total & 0x1) {
			return find_kth(A.begin(), m,
							B.begin(), n,
							total/2 + 1);
		} else {
			return (
					find_kth(A.begin(), m,
							B.begin(), n,
							total/2) + 
					find_kth(A.begin(), m,
							B.begin(),n,
							total/2 + 1)
					) / 2.0;
		}
}

private:
	static int find_kth(std::vector<int>::const_iterator A, int m,
						std::vector<int>::const_iterator B, int n,
						int k) {
		if (m > n) return find_kth(B, n, 
								   A, m, 
								   k);
		if (m == 0) return *(B + k - 1);
		if (k == 1) return min(*A, *B);

		int ia = min(k/2, m);
		int ib = k - ia;
		if (*(A + ia - 1) < *(B + ib - 1)) {
			return find_kth(A + ia, m - ia,
				            B, n,
				            k - ia);
		} else if (*(A + ia - 1) > *(B + ib - 1)) {
			return find_kth(A, m,
				            B + ib, n - ib,
				            k - ib);
		} else {
			return *(A + ia - 1);
		}
	}
};

Read More

2016-03-04
循环有序数组的查找

循环有序数组：

把一个有序数组从某个（未知）位置处截为两段，把前一段放到后一段的后面（数组元素两部分分别有序）
采用二分查找，时间复杂度要求O(log n)

主要难点：

二分查找时左右边界的确定
确定分割点之后，前半段和后半段中必然有一部分有序：

1
2
3
4
5
6
7
8
if(nums[first] <= nums[mid]) //前半部有序
{
//前半段有序时，判定target是否在前半段
}
else //后半部有序
{
//后半段有序时，判定target是否在后半段
}

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int first = 0;
        int last = nums.size();
        
        while (first != last) {
            const int mid = first + (last - first) / 2;
            if (nums[mid] == target) return mid;
            
            if (nums[first] <= nums[mid]) {
                if (nums[first] <= target && target < nums[mid]) {  // 改进：将target与first的判等独立出来
                    last = mid;
                } else {
                    first = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[last - 1]) { // 改进：将target与last-1的判等独立出来
                    first = mid + 1;
                } else {
                    last = mid;
                }
            }
        }
        
        return -1;
    }
};

若数组中允许存在重复元素：

nums[first] <= nums[mid]时，判断前半段有序的假设不再成立。如[2,3,4,2,2,2,2]。

解决：把条件拆分开

1
2
3
4
5
6
7
if (nums[first] < nums[mid]) {
	// 确定前半段有序
} else (nums[first] > nums[mid]) {
	// 确定后半段有序
} else {
	// ++first，去除一个重复
}
Read More

2016-03-04
从已排序数组删除冗余元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 要求冗余元素至多为N个。
class Solution {
public:
	int removeDuplicates(vector<int>& nums) {
		if (nums.size() < = N) return nums.size();

		int index = N;
		for (int i = N; i < nums.size(); i++) {
			if (nums[index - N] != nums[i]) {
				nums[index++] = nums[i];
			}
		}
		return index;
	}
};
Read More

2016-03-03
新的开始

勤做笔记、勤记忆。

Read More

2016-03-03
Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Read More
▲