数据结构刷题篇:第二天

简介: 数据结构刷题篇:第二天

一,两数之和


1. 两数之和 - 力扣(LeetCode)

https://leetcode.cn/problems/two-sum/

d03bc5d36f534d1da120cdeae7d3082e.png


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    }
};


1,暴力枚举:


如果找到两数之和,返回两数下标。


如果没找到,返回空。


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size()-1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return { i,j };
                }
            }
        }
        return {};
    }
};


复杂度分析


时间复杂度:O(N ^2 ),其中 NN 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。


空间复杂度:O(1)


2,哈希表


思路及算法


注意到方法一的时间复杂度较高的原因是寻找target 一x的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。使用哈希表,可以将寻找target 一x的时间复杂度降低到从O(N)降低到0(1)。这样我们创建一个哈希表, 对于每一个x,我们首先查询哈希表中是否存在target 一x,然后将x插入到哈希表中, 即可保证不会让x和自己匹配。


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};


复杂度分析


时间复杂度:O(N),其中 N 是数组中的元素数量。对于每一个元素 x,我们可以O(1) 地寻找 target - x。


空间复杂度:O(N),其中 N 是数组中的元素数量。主要为哈希表的开销。


二,合并两个有序数组


88. 合并两个有序数组 - 力扣(LeetCode)

https://leetcode.cn/problems/merge-sorted-array/

064764b547a04fd9b2f645b71cacc702.png


1,


最直观的方法是先将数组nums2放进数组 nums 1  的尾部,然后直接对整个数组进行排序。


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};


复杂度分析


●时间复杂度: 0((m + n)log(m + n))。

排序序列长度为m + n,套用快速排序的时间复杂度即可,平均情况为0(m + n)log(m + n))

●空间复杂度: O(log(m + n))。

排序序列长度为m + n,套用快速排序的空间复杂度即可,平均情况为O(log(m + n))。


2,双指针


算法


方法一没有利用数组nums 1  与 nums 2已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示:


332d326438779b6500a5289d28628b42.gif


我们为两个数组分别设置一个指针p1 与p2 来作为队列的头部指针。代码实现如下:


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = 0, p2 = 0;
        int sorted[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
};


复杂度分析


●时间复杂度: O(m + n)。

指针移动单调递增,最多移动m + n次,因此时间复杂度为O(m + n)。

●空间复杂度: O(m + n)。

需要建立长度为m + n的中间数组sorted。


3,逆向双指针


算法


方法二中,之所以要使用临时鼂,是因为如果直接合并到数组nums1中,nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums1中的元素呢?观察可知,nums1 的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进nums1的最后面。


严格来说,在此遍历过程中的任意一个时刻, nums1 数组中有m- p1 - 1个元素被放入nums1的后半部, .nums2数组中有n- p2- 1个元愫被放入nums1的后半部,而在指针p1的后面,nums1 数组有m+n-p1-1个位置。由于


m+n-P1-1≥m-P1一1+n-P2一1

等价于


P2≥-1


永远成立,因此p1后面的位置永远足够容纳被插入的元素,不会产生p1的元素被覆盖的情况。


实现代码如下:


class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};


复杂度分析


●时间复杂度: O(m + n)。

指针移动单调递减,最多移动m + n次,因此时间复杂度为O(m + n)。

●空间复杂度: O(1)。

直接对数组nums1原地修改,不需要额外空间。


以上部分来自本人在力扣的整理。

目录
相关文章
|
编译器 C语言
【数据结构刷题】消失的数字和轮转数组(下)
【数据结构刷题】消失的数字和轮转数组(下)
【数据结构刷题】消失的数字和轮转数组(上)
【数据结构刷题】消失的数字和轮转数组(上)
|
算法
数据结构刷题训练:用栈实现队列(力扣OJ)
数据结构刷题训练:用栈实现队列(力扣OJ)
61 0
|
5月前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
5月前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
|
5月前
|
算法
【数据结构与算法 刷题系列】移除链表元素
【数据结构与算法 刷题系列】移除链表元素