Chang

顺序

发表于 更新于 分类于 ， Valine：
本文字数： 13k 阅读时长 ≈ 12 分钟

leetcode 刷题记录，主要用 C++

1. 数组

1.1 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

题解

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& nums, int target) {
    for( int i = 0; i < nums.size(); i++){
        for( int j = i+1; j < nums.size(); j++ ){
            if (nums[i] + nums[j] == target)
            {
                return {i, j};
            }
        }
    }
    return{ };
}

暴力破解，直接对数组循环两边，每遍对应 twoSum 的一个数字。

1
2
3
4
5
6
7
8
9
vector<int> twoSumHash(vector<int>& nums, int target) {
    unordered_map<int,int> hashtable;
    for( int i = 0; i < nums.size(); i++){
        if( hashtable.end() != hashtable.find(target - nums[i]))
            return {hashtable[target - nums[i]], i};
        hashtable[nums[i]] = i;        
    }
    return {};
}

利用 hash 表的特性，将寻找 twoSum 中另外一个数的时间复杂度降为 O(1)，遍历一遍。
利用 HashMap，键放数组中具体的值，值放索引。
C++ 对应的 HashMap 是 unordered_map 容器。如果 find 方法没有找到对应的 key，返回 hashtablel.end()

1.2 删除有序数组中的重复项

题目描述

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明
为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int removeDuplicates(vector<int>& nums) {
    if (nums.size()==0)
    {
        return 0;
    }
        
    int index = 0;
    for(int i=1; i< nums.size(); ++i)
    {
        if(nums[index]!=nums[i])
        {
            ++index;
            nums[index] = nums[i];
        }
    }
    return index + 1;
}

双指针思想，第一个指针遍历原始数组，第二个指针指向去重后序列
按照题目描述，算法中 nums 应该只存有去重后的序列，而实际上官方的解决方案也没有对 nums 进行去重后对重复数据进行删除处理，目前想到的一种方案是使用 vector 的截取中间一段的函数，这要用到迭代器，可能会影响性能。或者再加一个迭代器，与第一个指针同步，用来实现原地删除。

1.3 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int removeElement(vector<int>& nums, int val) {
    int first = 0;
    int last = nums.size() - 1;

    while (first <= last)
    {
        if (nums[first] == val)
        {
            nums[first] = nums[first] ^ nums[last];
            nums[last] = nums[first] ^ nums[last];
            nums[first] = nums[first] ^ nums[last];
            last--;
        }
        else
        {
            first++;
        }
    }
    return first;
}
  1. 双指针思想
  2. 两个数交换，使用按位异或，实现交换。
    原理：一个数同另外一个属连续异或2次，可还原为它自己。
1
2
3
4
5
6
lhs = lhs ^ rhs ; // -1-
rhs = lhs ^ rhs ; // -2-
lhs = lhs ^ rhs ; // -3-

// -1- -2- 合并后即为　rhs = (lhs ^ rhs) ^ rhs
// -2- -3- 合并后即为　lhs = lhs ^ (lhs ^ rhs)

1.4 搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1：

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left = 0;
int right = nums.size()-1;
while(left <= right)
{
    int mid = left + ( right - left) / 2;
    // return left，= 的判断要放 right。如果 = 放 left 侧判断，当 nums[mid] == target 时，会执行下面 +1 语句，返回结果会多1
    if( nums[mid] < target )  
    {
        left = mid + 1;

    }else if( nums[mid] >= target )
    {
        right = mid - 1;
    }
}
return left;

二分查找思想

1.5 最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

题解

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
// 最大子序和
int maxSubArray(vector<int> &nums)
{
    // if (nums.size() == 1)
    //     return nums[0];
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.size(); i++)
    {
        if(currentSum < 0)
            currentSum = nums[i];
        else
            currentSum += nums[i];
        if( currentSum >= maxSum )
            maxSum = currentSum;
    }
    return maxSum;
}

// 最大子序和
int maxSubArray2(vector<int> &nums)
{
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.size(); i++)
    {
        currentSum = max( nums[i], currentSum+nums[i] );
        maxSum = max(currentSum,maxSum);
    }
    return maxSum;
}

核心点：如果当前序列和 < 0，则丢弃当前序列和，从下一元素重新开始计算；
再用另一个元素记录 maxSum。

2. HOT 100

2.1 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

题解

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& nums, int target) {
    for( int i = 0; i < nums.size(); i++){
        for( int j = i+1; j < nums.size(); j++ ){
            if (nums[i] + nums[j] == target)
            {
                return {i, j};
            }
        }
    }
    return{ };
}

暴力破解，直接对数组循环两边，每遍对应 twoSum 的一个数字。

1
2
3
4
5
6
7
8
9
vector<int> twoSumHash(vector<int>& nums, int target) {
    unordered_map<int,int> hashtable;
    for( int i = 0; i < nums.size(); i++){
        if( hashtable.end() != hashtable.find(target - nums[i]))
            return {hashtable[target - nums[i]], i};
        hashtable[nums[i]] = i;        
    }
    return {};
}

利用 hash 表的特性，将寻找 twoSum 中另外一个数的时间复杂度降为 O(1)，遍历一遍。
利用 HashMap，键放数组中具体的值，值放索引。
C++ 对应的 HashMap 是 unordered_map 容器。如果 find 方法没有找到对应的 key，返回 hashtablel.end()

2.2 两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,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
49
50
51
52
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head = nullptr;    // result 链表的头指针
    ListNode *tail = nullptr;    // result 链表的尾指针，用于新增 Node
    int carry = 0; //进位

    // 当两个链表都没有遍历完时
    while (l1 != nullptr && l2 != nullptr)
    {
        int sum = l1->val + l2->val + carry;
        if (head == nullptr)
        {
            head = tail = new ListNode(sum % 10);  // 开始构建 result 链表
        }
        else
        {
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        carry = sum / 10; // 更新进位

        l1 = l1->next;
        l2 = l2->next;
    }

    // l2 遍历完，而 l1 没有遍历完的情形
    while(l1 != nullptr)
    {
        // 注意仍然需要判断是否进位
        int sum = l1->val + carry;
        tail->next = new ListNode(sum%10);
        tail = tail->next;
        l1 = l1->next;
        carry = sum/10;
    }

    // l1 遍历玩，而 l2 没有遍历完的情形
    while(l2 != nullptr)
    {
        int sum = l2->val + carry;
        tail->next = new ListNode(sum%10);
        tail = tail->next;
        l2 = l2->next;
        carry = sum/10;
    }

    // 判断最后一位是否发生了进位
    if(carry!=0){
        tail->next = new ListNode(carry);
    }

    return head;
}

2.3 无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3

示例 2:

输入: s = “bbbbb”
输出: 1

示例 3:

输入: s = “pwwkew”
输出: 3

示例 4:

输入: s = “”
输出: 0

题解

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
int lengthOfLongestSubstring(string s)
{
    unordered_set<char> hashset;
    hashset.insert(s[0]);
    unsigned maxLength = 1;
    unsigned int left = 0; // 用来标识当前无重复字符串的起始位置

    for (unsigned right = 1; right < s.size(); right++)
    {
        if (!hashset.count(s[right])) // hashset 不存在当前字符
        {
            hashset.insert(s[right]);
            maxLength = max(maxLength, right - left + 1);
        }
        else
        {
            if (hashset.size() == 1)
            {
                left++;
                continue;
            }
            hashset.erase(s[left]);
            left++;
            // maxLength = max( maxLength, right-left);
            while (hashset.count(s[right]) > 0) // 当前字符还与目前字符串有重复字符
            {
                hashset.erase(s[left]); // 去除无重复字符串最左侧字符
                left++;
            }
            hashset.insert(s[right]);
        }
     }
    return maxLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(string s) {
    unordered_set<char> hashset;
    int right = -1;  // 相当于滑动窗口右边边界。初始时滑动窗口还不存在，为-1。 
    int maxLength = 0;
    for (int left = 0; left < s.size(); left++)
    {
        if( left != 0  )
            hashset.erase(s[left-1]);    // 滑动窗口左侧向右移动一个位置
        while ( right + 1 < s.size() && !hashset.count(s[right+1]) )   // 只有当滑动窗口下一个元素不在滑动窗口内时，才加入滑动窗口，并且滑动窗口右侧扩1
        {
            hashset.insert(s[right+1]);
            right++;
        }
        maxLength = max(maxLength, right-left+1);
    }
    return maxLength;
}

2.4 寻找两个正序数组的中位数

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000

示例 2：

输入：nums1 = [], nums2 = [1]
输出：1.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶：

你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

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
double findMedianSortedArrays1(vector<int> &nums1, vector<int> &nums2)
{
    int indexSum = nums1.size() + nums2.size();
    int midIndex = indexSum / 2;
    vector<int> nums; // 合并 num1,num2
    unsigned i = 0;
    unsigned j = 0;
    unsigned k = 0;

    // 其中一个数组为空
    if (nums1.size() == 0)
        nums = nums2;
    if (nums2.size() == 0)
        nums = nums1;

    nums.resize(indexSum); // 两个数组都不为空，调整合并数组大小

    // 遍历两个待合并数组，直至其中一个数组遍历完
    while (i < nums1.size() && j < nums2.size())
    {
        if (nums1[i] > nums2[j])
        {
            nums[k] = nums2[j];
            j++;
        }
        else
        {
            nums[k] = nums1[i];
            i++;
        }
        k++;
    }

    while (i < nums1.size())
    {
        nums[k] = nums1[i];
        i++;
        k++;
    }

    while (j < nums2.size())
    {
        nums[k] = nums2[j];
        j++;
        k++;
    }

    // 返回合并数组的中位数
    if (indexSum % 2 != 0) // 奇
        return nums[midIndex];
    else // 偶
        return (nums[midIndex] + nums[midIndex - 1]) / 2.0;
}

第一种方法，对两个数组直接进行合并，然后返回中位数

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
// 我们不需要合并的数组，实际上只要知道中位数在就行了。
// 开始的思路是进行一次完整的遍历，当到达中位数这个位置时就返回，但这里对奇偶以及边界判断会很麻烦，代码很乱，并且时间复杂度与第一种方法不变。
// 可以在循环处判断到中位数那个位置，同时记录下上一次遍历和这一次遍历的结果。对于奇，中位数就是当前位置，对于偶，就是与上一次结果的平均。
double findMedianSortedArrays2(vector<int> &nums1, vector<int> &nums2)
{
    int indexSum = nums1.size() + nums2.size();
    int midIndex = indexSum / 2 + 1; // 中位数的位置，非索引
    int left = 0;                    // 上一轮的值
    int right = 0;                   // 当前遍历的值
    int start1 = 0;                  // 第一个数组遍历索引
    int start2 = 0;                  // 第二个数组遍历索引
    for (unsigned i = 0; i < midIndex; i++)
    {
        left = right;
        // 需要先判断 nums1 是否为空，否则当 nums1 为空时，nums1[start1] 将会越界
        // 后部分需要先判断 start2 是否已经遍历完或者为空，否则 nums2[start2]会越界
        if (start1 < nums1.size() && (start2 >= nums2.size() || nums1[start1] < nums2[start2]))
        {
            right = nums1[start1];
            start1++;
        }
        else
        {
            right = nums2[start2];
            start2++;
        }
    }

    if (indexSum % 2 != 0)
    {
        return right;
    }
    else
    {
        return (left + right) / 2.0;
    }
}
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
// 用的是二分法查找两个数组中第 k 小的数
double findMedianSortedArrays3(vector<int> &nums1, vector<int> &nums2)
{
    int n = nums1.size();
    int m = nums2.size();
    // 将奇偶统一。如果总数是奇数，那个 left == right
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    // 返回第 left 小 和第 right 小的数的平均值
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) / 2.0;  
}

// start、end 是索引，k指第几小 Kth
int getKth(vector<int> nums1, int start1, int end1, vector<int> nums2, int start2, int end2, int k)
{
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;

    // 递归出口：其中一个数组为空，或者 k = 1，即求最小的数
    // 确保当存在数组为空时，一定是 nums1
    if ( len2 < len1 )  // 两个数组交换位置
        return getKth(nums2, start2, end2, nums1, start1, end1, k);

    if(len1 == 0)
        return nums2[start2 + k - 1];
    
    if(k == 1)  // 即返回最小的一个数
        return min(nums1[start1], nums2[start2]);

    // 取两个数组第 k/2 的索引。还需要判断 k/2 是否超过数组长度 len 的情况
    int i = start1 + min(k/2, len1) - 1;
    int j = start2 + min(k/2, len2) - 1;

    // 从找第 k 小变成了 第 (k - 弃掉数个数)小了
    // 弃掉数可能是 k/2，也有可能是 len 长度
    if ( nums1[i] > nums2[j] )  
    {
        return getKth( nums1, start1, start2, nums2, j + 1, end2, k-( j - start2 + 1) );
    }else{
        return getKth( nums1, i + 1, end1, nums2, start2, end2, k - ( i - start1 + 1 ) );
    }
}

思路源于 leetcode 作者：windliang，链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

解法二中，我们一次遍历就相当于去掉不可能是中位数的一个值，也就是一个一个排除。由于数列是有序的，其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。看下边一个例子。

假设我们要找第 7 小的数字。

我们比较两个数组的第 k/2 个数字，如果 k 是奇数，向下取整。也就是比较第 33 个数字，上边数组中的 44 和下边数组中的 33，如果哪个小，就表明该数组的前 k/2 个数字都不是第 k 小数字，所以可以排除。也就是 11，22，33 这三个数字不可能是第 77 小的数字，我们可以把它排除掉。将 13491349 和 4567891045678910 两个数组作为新的数组进行比较。

更一般的情况 A[1] ，A[2] ，A[3]，A[k/2] … ，B[1]，B[2]，B[3]，B[k/2] … ，如果 A[k/2]<B[k/2] ，那么A[1]，A[2]，A[3]，A[k/2]都不可能是第 k 小的数字。

A 数组中比 A[k/2] 小的数有 k/2-1 个，B 数组中，B[k/2] 比 A[k/2] 小，假设 B[k/2] 前边的数字都比 A[k/2] 小，也只有 k/2-1 个，所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个，所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了，所以可以把它们排除。

橙色的部分表示已经去掉的数字。

由于我们已经排除掉了 3 个数字，就是这 3 个数字一定在最前边，所以在两个新数组中，我们只需要找第 7 - 3 = 4 小的数字就可以了，也就是 k = 4。此时两个数组，比较第 2 个数字，3 < 5，所以我们可以把小的那个数组中的 1 ，3 排除掉了。

我们又排除掉 2 个数字，所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数，4 == 4，怎么办呢？由于两个数相等，所以我们无论去掉哪个数组中的都行，因为去掉 1 个总会保留 1 个的，所以没有影响。为了统一，我们就假设 4 > 4 吧，所以此时将下边的 4 去掉。

由于又去掉 1 个数字，此时我们要找第 1 小的数字，所以只需判断两个数组中第一个数字哪个小就可以了，也就是 4。

所以第 7 小的数字是 4。

我们每次都是取 k/2 的数进行比较，有时候可能会遇到数组长度小于 k/2的时候。

此时 k / 2 等于 3，而上边的数组长度是 2，我们此时将箭头指向它的末尾就可以了。这样的话，由于 2 < 3，所以就会导致上边的数组 1，2 都被排除。造成下边的情况。

由于 2 个元素被排除，所以此时 k = 5，又由于上边的数组已经空了，我们只需要返回下边的数组的第 5 个数字就可以了。

从上边可以看到，无论是找第奇数个还是第偶数个数字，对我们的算法并没有影响，而且在算法进行中，k 的值都有可能从奇数变为偶数，最终都会变为 1 或者由于一个数组空了，直接返回结果。

所以我们采用递归的思路，为了防止数组长度小于 k/2，所以每次比较 min(k/2，len(数组) 对应的数字，把小的那个对应的数组的数字排除，将两个新数组进入递归，并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。