4. 寻找两个正序数组的中位数

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
49
50
51
52
53
54
//二分查找
//写一个查找第k大的函数，k值在运行过程中会慢慢减小
int findKthElement(vector<int>& nums1, vector<int>& nums2, int k)
{
    int m = nums1.size();
    int n = nums2.size();
    int index1 = 0;
    int index2 = 0;
    while (true)
    {
        //nums1中的指针位置已经到了末尾，直接在num2中找剩下的第k大
        if (index1 == m)
        {
            return nums2[index2 + k - 1];
        }
        if (index2 == n)
        {
            return nums1[index1 + k - 1];
        }
        if (k == 1)
        {
            return min(nums1[index1], nums2[index2]);
        }
		//边界检测，index如果加了k / 2 - 1越界了，就直接将新的index设置为数组的最后一位
        int newIndex1 = min(index1 + k / 2 - 1, m - 1);
        int newIndex2 = min(index2 + k / 2 - 1, n - 1);
        int pivot1 = nums1[newIndex1];
        int pivot2 = nums2[newIndex2];
        if (pivot1 <= pivot2)
        {
            //更新k和index
            k -= newIndex1 - index1 + 1;
            index1 = newIndex1 + 1;
        }
        else
        {
            k -= newIndex2 - index2 + 1;
            index2 = newIndex2 + 1;
        }
    }
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int totalLength = nums1.size() + nums2.size();
    if (totalLength % 2 == 1)
    {	//奇数总数和偶数总数分开讨论
        return findKthElement(nums1, nums2, (totalLength + 1) / 2);
    }
    else
    {
        return (findKthElement(nums1, nums2, totalLength / 2) + findKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
    }

}

34. 在排序数组中查找元素的第一个和最后一个位置

排序数组直接联想二分查找

对二分查找做适合题目要求的改动，有多个连续的target值，寻找左边界时要找到最左面的target下标，则需要在findLeft函数中添加判断：

1
2
if(nums[mid] == target)
	right = mid;

使有边界逐渐向左逼近，以保证最后走出 while(left < right) 循环时，left在多个相同的target中的最左面

在findRight函数中不仅需要添加判断：

1
2
if(nums[mid] == target)
	left = mid;

特别注意，还需要修改mid的计算：

1
mid = (left + right + 1) / 2

这里如果不加1的话，当left == right-1时，计算mid永远等于left，无法退出循环

347. 前 K 个高频元素

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
// 这里的static的添加是因为sory()第三个参数是个函数指针，然而cmp函数是一个非静态成员函数，非静态成员函数指针和普通函数指针是有区别的，为防止报错在类内的成员函数定义前添加static，或者把cmp函数定义写在类外
static bool cmp(pair<int,int> a, pair<int,int> b)
    {
        return a.second > b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> countMap;
        int n = nums.size();
        map<int, int>::iterator it;
        for(int i = 0; i < n; i++)
        {
            // 判断map中某个key是否存在，使用find()，（find()返回的是迭代器）
            it = countMap.find(nums[i]);
            if(it != countMap.end())
            {
                countMap[nums[i]]++;
            }
            else
            {
                // map中插入新的<key, value>对
                countMap.insert(pair<int,int>(nums[i], 1));
            }
        }
        // map没有sort()函数，因为map不是线性结构，所以为了排序，将map中的pair形式的成员放到vector中再进行排序
        vector<pair<int,int>> vec;
        for(map<int,int>::iterator it = countMap.begin(); it != countMap.end(); it++)
        {
            vec.push_back(pair<int,int>(it->first, it->second));
        }
        sort(vec.begin(), vec.end(), cmp);
        vector<int> res;
        vector<pair<int,int>>::iterator iter = vec.begin();
        while(k)
        {
            res.push_back(iter->first);
            iter++;
            k--;
        }
        return res;
    }