数组总结

程序员文章站 2022-03-22 08:10:16

...

哈希

两数之和:easy

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

维护一个hash表，边遍历数组边存储值到hash表中，当遍历到nums[i]时，如果hash[target - nums[i]] > 0，那么就找到了符合条件的两个值

时间复杂度：O(n)
空间复杂度：O(n)

C++代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++) {
            if(hash.count(target - nums[i]) != 0) {
                res[0] = hash[target - nums[i]];
                res[1] = i;
                break;
            }
            hash[nums[i]] = i;
        }
        return res;
    }
};

两个数组的交集:easy

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
方法1

将数组nums1的元素放入一个set中，然后遍历nums2的元素nums2[i]，判断它是否在set中，如果在set中，则说明这个元素是交集的部分，将它加入结果中。

设nums1的大小为m，数组nums2的大小为n

时间复杂度：O(m + n)
空间复杂度：O(m)

C++代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() || nums2.empty())
            return vector<int>();
        
        unordered_set<int> st;
        for(auto a : nums1)
            st.insert(a);
        
        vector<int> res;
        for(int a : nums2)
        {
            if(st.count(a) > 0)
            {
                res.push_back(a);
                st.erase(a);
            }
        }
        
        return res;
    }
};

方法2：排序 +双指针

先将nums1和nums2排序(从小到大排序)，维护一个set存放交集元素，定义两个指针p1和p2分别从nums1和nums2出发，处理情况如下：

如果nums1[p1] == nums2[p2]，则将numns[p1]放入set，同时++p1,++p2；
否则，nums1[p1] < nums2[p2] ? ++p1 : ++p2。

直到p1或p2到达数组尾部。

最后将set中的元素放入结果数组中即可。

设nums1的大小为m，数组nums2的大小为n

时间复杂度：O(m log m + n log n)
空间复杂度：O(max(m,n))

C++代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        
        vector<int> res;
        set<int> st;
        int p1 = 0,p2 = 0;
        while(p1 < nums1.size() && p2 < nums2.size())
        {
            if(nums1[p1] == nums2[p2])
            {
                st.insert(nums1[p1]);
                ++p1;
                ++p2;
            }
            else{
                nums1[p1] < nums2[p2] ? ++p1 : ++p2;
            }
        }
        
        for(auto a : st) res.push_back(a);
        
        return res;
    }
};

方法3

现将nums1从小到大排序，遍历数组nums2的每一个元素nums2[i]，同时在nums1中二分查找nums2[i]，如果能找到nums2[i]，则将它加入set中；否则，跳过。最后，将set中的元素放入结果数组即可。

设nums1的大小为m，数组nums2的大小为n

时间复杂度：O((m + n) log m)
空间复杂度：O(min(m,n))

C++代码

class Solution {
public:
    bool binarySearch(const vector<int>& vec,int target)
    {
        int l = 0,r = vec.size() - 1;
        while(l <= r)
        {
            int m = (l + r) / 2;
            if(vec[m] < target) l = m+1;
            else if(vec[m] > target) r = m-1;
            else return true;
        }
        
        return false;
    }
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        
        set<int> st;
        vector<int> res;
        for(auto a : nums2)
        {
            if(binarySearch(nums1,a))
                st.insert(a);
        }
        
        for(auto a : st) res.push_back(a);
        
        return res;
    }
};

两个数组的交集II:easy

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
方法1

用unordered_map（无序哈希表）来建立nums1中字符和其出现个数之间的映射, 然后遍历nums2数组，如果当前字符在哈希表中的个数大于0，则将此字符加入结果中，然后哈希表的对应值自减1。

设nums1的大小为m，数组nums2的大小为n

时间复杂度：O(m + n)
空间复杂度：O(max(m,n))

C++代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int,int> mp;
        
        for(auto a : nums1) ++mp[a];
        for(auto b : nums2)
        {
            if(mp[b] > 0)
            {
                res.push_back(b);
                --mp[b];
            }
        }
        
        return res;
    }
};

优化空间：哈希表统计两数组中长度较小的那个数组的元素个数。

时间复杂度：O(m + n)
空间复杂度：O(min(m,n))

C++代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        
        unordered_map<int,int> mp;
        
        if(nums1.size() > nums2.size())
        {
            //长度较小的数组拷贝到临时数组
            vector<int> tmp(nums2);
            nums2 = nums1;
            nums1 = tmp;
        }
        
        for(auto a : nums1) ++mp[a];
        for(auto b : nums2)
        {
            if(mp[b] > 0)
            {
                res.push_back(b);
                --mp[b];
            }
        }
        
        return res;
    }
};

方法2

先将nums1和nums2排序(从小到大排序)，定义两个指针p1和p2分别从nums1和nums2出发，处理情况如下：

如果nums1[p1] == nums2[p2]，则将numns[p1]放入结果，同时++p1,++p2；
否则，nums1[p1] < nums2[p2] ? ++p1 : ++p2。

直到p1或p2到达数组尾部。

设nums1的大小为m，数组nums2的大小为n

时间复杂度：O(m log m + n log n)
空间复杂度：O(max(m,n))

C++代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        
        vector<int> res;
        int p1 = 0,p2 = 0;
        while(p1 < nums1.size() && p2 < nums2.size())
        {
            if(nums1[p1] == nums2[p2])
            {
                res.push_back(nums1[p1]);
                ++p1;
                ++p2;
            }
            else{
                nums1[p1] < nums2[p2] ? ++p1 : ++p2;
            }
        }
        
        return res;
    }
};

存在重复元素:easy

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

利用unordered_set无序集合，遍历数组的时候将元素放入集合中，找出已经在集合中出现的元素就是重复的元素

时间复杂度：O(n)
空间复杂度：O(n)

C++代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.empty())
            return false;
        
        int len=nums.size();
        unordered_set<int> st;
        for(auto a:nums)
        {
            if(st.find(a) != st.end())
                return true;
            else
                st.insert(a);
        }
        
        return false;
    }
};

求众数:easy

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

方法1：哈希表

基于原数组建立哈希表，key为元素，value为元素个数，找出value > len/2的元素就是众数

时间复杂度：O(n)
空间复杂度：O(n)

C++代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> mp;
        int len = nums.size();
        int res = INT_MIN;
        for(auto a : nums)
        {
            mp[a]++;
            if(mp[a] > len/2) 
            {
                res = a;
                break;
            }
        }
        
        return res;
    }
};

方法2：摩尔投票法

参见博客

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0;
        int res = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(cnt == 0)
            {
                cnt++;
                res = nums[i];
            }
            else if(nums[i] == res)
                cnt++;
            else
                cnt--;
        }
        
        return res;
        
    }
};

有效的数独:medium

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫格内只能出现一次。

数组总结

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

解答

要判断是否出现重复元素，只需要遍历的时候用哈希表记录每一个字符ch(介于'1'~'9'之间)出现的次数，当字符再次出现的时候判断ch在哈希表中的次数是否大于0，就可以判断是否出现重复的字符。由于在每一行、每一列和每一个3x3宫格内都不能出现重复的字符，那么需要以逐行、逐列和逐个3x3宫格的方式分别遍历，同时利用哈希表记录并判断，便能得出结果。

时间复杂度：O(9x9) = O(1)
空间复杂度：O(9) = O(1)

C++代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_map<char,int> mp;
        int row = board.size();
        int col = board[0].size();
        
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                int ch = board[i][j];
                if(ch != '.')
                {
                    mp[ch]++;
                    if(mp[ch] > 1)
                        return false;
                }
            }
            
            mp.clear();
        }
        
        for(int i=0;i<col;i++)
        {
            for(int j=0;j<row;j++)
            {
                char ch = board[j][i];
                if(ch != '.')
                {
                    mp[ch]++;
                    if(mp[ch] > 1)
                        return false;
                }
            }
            
            mp.clear();
        }
        
        for(int i=0;i<row;i+=3)
        {
            for(int j=0;j<col;j+=3)
            {
                for(int x=i;x<i+3;x++)
                    for(int y=j;y<j+3;y++)
                    {
                        char ch=board[x][y];
                        if(ch != '.')
                        {
                            mp[ch]++;
                            if(mp[ch] > 1)
                                return false;
                        }
                    }
                
                mp.clear();
            }
        }
        
        return true;
    }
};

双指针

三数之和:medium

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

对整个数组排序，先遍历数组取三数中的第一个数nums[i]，注意num[i]只到数组的倒数第三个元素，然后剩下两个数需要满足条件target = 0 - nums[i],这两个数在数组中num[i]后面部分，维持两个双指针l和r，令tmp = nums[l] + nums[r]，处理情况如下：

如果tmp < target，则l右移一步；
如果tmp > target，则r左移一步；
否则，满足条件，添加两个数到结果数组中，同时将l和r分别右移和左移到下一个不重复的元素处。

注意：遍历数组的时候取第一个数的时候过滤重复元素，可以提高查找效率

时间复杂度：O(n²)
空间复杂度：O(1)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        if(len < 3)
            return vector<vector<int>>();
        
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        for(int i=0;i<len-2;i++)
        {
            if(i == 0 || (i > 0 && nums[i] != nums[i-1]))
            {
                int l = i+1;
                int r = len-1;
                int target = 0 - nums[i];
                while(l < r)
                {
                    int tmp = nums[l] + nums[r];
                    if(target > tmp)
                    {
                        l++;
                    }
                    else if(target < tmp)
                    {
                        r--;
                    }
                    else{
                        res.push_back({nums[i],nums[l],nums[r]});
                        l++;
                        r--;
                        while(l < r && nums[l] == nums[l-1])
                            l++;
                        while(l < r && nums[r] == nums[r+1])
                            r--;
                    }
                }
                
            }
        }
        
        return res;
    }
};

最接近的三数之和:medium

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

思路和三数之和类似：先排序数组，遍历数组取第一个数(只到数组倒数第三个元素)，剩下两个数在第一个数的右边部分，定义双指针l和r分别指向i+1和len-1，当前三数和tmp = nums[l] + nums[r] + nums[i]，然后向中间移动，移动规则如下：

如果tmp < target，则++l，同时比较abs(tmp - target)和abs(res - target)，取较小值对应的那个三数和给结果res
如果tmp > target，则–r，同时比较abs(tmp - target)和abs(res - target)，取较小值对应的那个三数和给结果res
如果tmp == target，则tmp即为所求

时间复杂度：O(n²)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        if(len < 3) return INT_MAX;
        
        int res = nums[0] + nums[1] + nums[2];
        
        for(int i=0;i<len-2;i++)
        {
            if(i == 0 || nums[i] != nums[i-1])
            {
                int l = i+1,r = len-1;
                while(l < r)
                {
                    int tmp = nums[l] + nums[r] + nums[i];
                    if(tmp < target)
                    {
                        res = abs(res - target) < abs(target - tmp) ? res : tmp;
                        ++l;
                    }
                    else if(tmp > target)
                    {
                        res = abs(res - target) < abs(target - tmp) ? res : tmp;
                        --r;
                    }
                    else{
                        return tmp;
                    }
                    
                    if(i > 0)
                    {
                        while(l < r && nums[l] == nums[l-1]) ++l;
                        while(l < r && nums[r] == nums[r+1]) --r;
                    }
                }
            }
            
        }
        
        return res;
    }
};

四数之和:medium

双指针

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>>res;
        if(nums.size()<4)
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-3;i++)
        {
            if(i>0 && nums[i]==nums[i-1])//去除重复
                continue;
            for(int j=i+1;j<(int)nums.size()-2 ;j++)
            {
                if(j>i+1 && nums[j]==nums[j-1])//去除重复
                    continue;
                int left=j+1;
                int right=nums.size()-1;
                while(left<right)
                {
                    int temp=nums[i]+nums[j]+nums[left]+nums[right];
                    if(temp==target)
                    {
                        res.push_back({nums[i],nums[j],nums[left],nums[right]});
                        while(left<right && nums[left]==nums[left+1])//去除重复
                            left++;
                        while(left<right && nums[right]==nums[right-1])//去除重复
                            right--;
                        left++;
                        right--;
                    }
                    else if(temp<target)
                        left++;
                    else
                        right--;
                }
            }
        }

        return res;
        
    }
};

删除排序数组中的重复项：easy

26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

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

示例 1:

给定数组 nums = [1,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。

你不需要考虑数组中超出新长度后面的元素。

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

        return j+1;
    }
};

移动零：easy

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

双指针法，快指针i遍历一遍数组，当快指针的元素非零时，令慢指针idx的元素等于快指针元素，同时慢指针前进一步。最后，所有的非零元素都移到了数组前半部分（相对顺序不变），然后将之后的元素全部置0。

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.empty())
            return;
        
        int idx = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i] != 0)
            {
                nums[idx++] = nums[i];
            }
        }
        
        for(;idx<nums.size();idx++)
            nums[idx] = 0;
        
        return;
    }
};

判断子序列:medium

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace“是”abcde“的一个子序列，而”aec"不是）。

示例 1:

s = “abc”, t = “ahbgdc”

返回 true.

示例 2:

s = “axc”, t = “ahbgdc”

返回 false.

后续挑战 :

如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

双指针法，设置指针i和j分别指向字符串s和t

如果s[i] == t[j]，则i前进一步，j前进一步
否则，j前进一步

最后，判断指针i是否走完s，就能判断s是否为t的子序列。

时间复杂度：O(m+n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len = s.size();
        int len1 = t.size();
        
        if(len > len1) return false;
        int i = 0,j = 0;
        while(i < len && j < len1)
        {
            if(s[i] == t[j])
            {
                i++;
               
            }
            
            j++;
        }
        
        if(i == len) return true;
        return false;
    }
};

盛最多水的容器：medium

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

数组总结

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

双指针法，定义两个指针l和r分别指向数组两端，两个指针向中间移动，移动规则如下：

如果height[l] < height[r]，则++l
否则，–r

每走一步，计算容器装水量为左右边缘较小的那个高度乘边缘的的距离min(height[l],height[r]) * (r - l),然后和结果比较去较大值。

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int len = height.size();
        if(len == 0) return 0;
        
        int res = 0;
        int l = 0;
        int r = len - 1;
        while(l < r)
        {
            int tmp = min(height[l],height[r]);
            int sum = (r - l)*tmp;
            if(height[l] < height[r])
                ++l;
            else
                --r;
            
            res = max(res,sum);
            
            while(l < r && tmp == height[l]) ++l;
            while(l < r && tmp == height[r]) --r;
        }
        
        return res;
    }
};

合并两个有序数组：easy

合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

双指针法，思路同合并两个有序链表

时间复杂度：O(m + n)
空间复杂度：O(m + n)

C++代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       for(int i=m,j=0;i<m+n ;i++)
           nums1[i] = nums2[j++];
        
        vector<int> vec(m + n,0);
        
        int l = 0;
        int r = m;
        int cnt = 0;
        while(l < m && r < m + n)
        {
            vec[cnt++] = nums1[l] < nums1[r] ? nums1[l++] : nums1[r++];
        }
        
        while(l < m)
            vec[cnt++] = nums1[l++];
        while(r < m + n)
            vec[cnt++] = nums1[r++];
        
        copy(vec.begin(),vec.end(),nums1.begin());
    }
};

找规律

螺旋矩阵：medium

54. 螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int>res;
        if(matrix.empty())
            return res;
        int top=0,bottom=matrix.size()-1,left=0,right=matrix[0].size()-1;
        while(top<=bottom && left<=right)
        {
            for(int i=left;i<=right;i++)
            {
                res.push_back(matrix[top][i]);
            }
            for(int i=top+1;i<=bottom;i++)
                res.push_back(matrix[i][right]);
            for(int i=right-1;i>=left && bottom>top;i--)
                res.push_back(matrix[bottom][i]);
            for(int i=bottom-1;i>top && right>left;i--)
                res.push_back(matrix[i][left]);
            top++;
            bottom--;
            left++;
            right--;
        }

        return res;


    }
};

螺旋矩阵II：medium

LeetCode中文

LeetCode英文

给定一个正整数 n，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

思路和螺旋矩阵相同，还是分层处理，不过螺旋矩阵是从矩阵读取值，这一题是写入值到矩阵。可以定义一个变量cnt用于全局计数，直到cnt等于n²的时候终止写入。

时间复杂度：O(n²)
空间复杂度：O(n²)

C++代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>>res(n,vector<int>(n));

        int top=0,bottom=n-1,left=0,right=n-1;
        int j=1;
        while(top<=bottom  && left<=right)
        {
            for(int i=left;i<=right;i++)
            {
                res[top][i]=j;
                j++;
            }
            for(int i=top+1;i<=bottom;i++)
            {
                res[i][right]=j;
                j++;
            }
            for(int i=right-1;i>=top && top<bottom;i--)
            {
                res[bottom][i]=j;
                j++;
            }
            for(int i=bottom-1;i>top && left<right;i--)
            {
                res[i][left]=j;
                j++;
            }
            top++;
            bottom--;
            left++;
            right--;
        } 

        return res;

    }
};

旋转图像：medium

48. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:

给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();

        // transpose matrix
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                int tmp = matrix[j][i];
                matrix[j][i] = matrix[i][j];
                matrix[i][j] = tmp;
            }
        }
    // reverse each row
        for (int i = 0; i < n; i++) 
        {
           for (int j = 0; j < n / 2; j++) 
            {
               int tmp = matrix[i][j];
               matrix[i][j] = matrix[i][n - j - 1];
               matrix[i][n - j - 1] = tmp;
            }

        }
    }
};

矩阵置零：medium

73. 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2:

输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.empty())
            return;
        int m=matrix.size();
        int n=matrix[0].size();
        set<int>row,cols;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(matrix[i][j]==0)
                {
                    row.insert(i);
                    cols.insert(j);
                }
            }
        }

        // for(int i=0;i<m;i++)
        // {
        //     for(int j=0;j<n;j++)
        //     {
        //         if(row.find(i)!=row.end() || cols.find(j)!=cols.end())
        //             matrix[i][j]=0;
        //     }
        // }

        set<int>::iterator it;
        for(int i=0;i<m;i++)
        {
            for(it=cols.begin();it!=cols.end();it++)
                matrix[i][*it]=0;
        }
        for(int i=0;i<n;i++)
        {
            for(it=row.begin();it!=row.end();it++)
                matrix[*it][i]=0;
        }
    }
};

除自身以外数组的乘积：medium

238.除自身以外数组的乘积

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：

你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

方法1

由于output[i] = nums[0]*nums[1]*...*nums[i-1]*nums[i+1]*...*nums[len-1],可以将output[i]分为两部分，前半部分为C[i] = nums[0]*nums[1]*...*nums[i-1],后半部分为D[i] = nums[i+1]*...*nums[len-1]。可以发现规律，数组C和D相邻元素之间存在递推关系：

C[i] = C[i-1]*nums[i-1] (i = 1~len-1)
D[i] = D[i+1]*nums[i+1] (i = 0~len-2)

因此求出数组output的每一项output[i] = C[i]*D[i]。

时间复杂度：O(n)
空间复杂度：O(n)

C++代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return nums;
        
        vector<int> res(len,1);
        vector<int> C(len,1);
        vector<int> D(len,1);
        for(int i=1;i<len;i++)
        {
            C[i] = nums[i-1]*C[i-1];
        }
        
        for(int i=len-2;i>=0;i--)
        {
            D[i] = D[i+1]*nums[i+1];
        }
        
        for(int i=0;i<len;i++)
        {
            res[i] = C[i]*D[i];
        }
        
        return res;
    }
};

方法2：优化空间复杂度

先将数组C的数值计算到输出数组res中，然后定义一个变量tmp代替数组D的递推关系计算，对数组res从后向前进行递推计算得出最终结果。可以优化空间复杂度到常数时间。

时间复杂度：O(n) (输出数组不被视为额外空间)
空间复杂度：O(1)

C++代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return nums;
        
        vector<int> res(len,1);
        for(int i=1;i<len;i++)
        {
            res[i] = res[i-1] * nums[i-1];
        }
        
        int tmp = 1;
        for(int i=len-2;i>=0;i--)
        {
            tmp *= nums[i+1];
            res[i] *= tmp; 
        }
        
        return res;
    }
};

搜索二维矩阵：medium，二分查找

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        if(m==0)
            return false;
        int n=matrix[0].size();
        int left=0,right=m*n-1;
        int mid,mid_matrix;
        while(left<=right)
        {
            mid=(left+right)/2;
            mid_matrix=matrix[mid/n][mid%n];
            if(target==mid_matrix)
                return true;
            else if(target<mid_matrix)
                right=mid-1;
            else
                left=mid+1;

        }
        return false;    
    }
};

        if(matrix.empty())
            return false;
        int row=0;
        int column=matrix[0].size()-1;
        while(row<matrix.size()&& column>=0)
        {
            if(target==matrix[row][column])
                return true;
            else if(target<matrix[row][column])
                column--;
            else
                row++;
        }
        return false;

其它

杨辉三角：easy

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

数组总结

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

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

解答

利用杨辉三角的性质，利用上一行的数值推导出下一行，推导关系式为：

时间复杂度：O(n²)
空间复杂度：O(n²)

C++代码

class Solution {
public:
    vector<int> transform(vector<int> vec)
    {
        vector<int> res;
        res.push_back(1);
        int len = vec.size();
        for(int i=1;i<len;i++)
        {
            res.push_back(vec[i-1] + vec[i]);
        }
        
        res.push_back(1);
        return res;
        
    }
    
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if(numRows == 0)
            return res;
        if(numRows == 1)
        {
            res.push_back({1});
            return res;
        }
        
        res.push_back({1});
        for(int i=1;i<numRows;i++)
        {
            res.push_back(transform(res[i-1]));
        }
        
        return res;
    }
};

Python代码

缺失数字：easy

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:

你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

方法1：位运算

将原数组的所有元素和0~n的所有数字做异或运算，得到结果就是缺失的数字

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0;i<nums.size();i++)
        {
            res ^= (i + 1) ^ nums[i];
        }
        
        return res;
    }
};

方法2：等差数列

等差数列求0~n的和减去数组所有元素相加得到的和即为缺失的数字

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        for(auto num : nums) sum += num;
        return (int)((1 + n) * n / 2) - sum;
    }
};

旋转数组：easy

189.旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。

方法1

设数组的长度为len，k对len取模得到k1 = k % len，开辟一个新数组cp拷贝nums，nums的值清空，然后进行如下步骤：

将cp数组的最后k1个元素添加到数组nums尾部
将cp数组的开始len-k1个元素添加到数组nums尾部

时间复杂度：O(n)
空间复杂度：O(n)

C++代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        int k1 = k%len;
        
        vector<int> cp(nums);
        nums.clear();
        
        copy(cp.end() - k1,cp.end(),back_inserter(nums));
        copy(cp.begin(),cp.end() - k1,back_inserter(nums));
    }
};

方法2

设数组的长度为len，k对len取模得到k1 = k % len，然后进行如下步骤：

反转数组的最后k1个元素
反转数组的前面len - k1个元素
反转整个数组

最后得到的数组的就是旋转之后的数组

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(k == nums.size())
            return;
        
        int len = nums.size();
        int k1 = k % len;
        
        reverse(nums.begin(),nums.end() - k1);
        reverse(nums.end() - k1,nums.end());
        reverse(nums.begin(),nums.end());
    }
};

寻找重复数：medium

278.寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n²) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

遍历数组，判断当前元素nums[i]是否和位置i+1相等：

如果nums[i] == i+1，则nums[i]位于它自己的位置，++i遍历下一个元素；
否则，找到位置是nums[i]-1位置的元素nums[nums[i] - 1]：
- 如果nums[nums[i] - 1] == nums[i],则找到重复元素nums[i]
- 否则，交换nums[nums[i] - 1]和nums[i]
  重复情况2的过程，直到nums[i] == i+1时，执行情况1。

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if(nums.empty())
            return 0;
        
        for(int i=0;i<nums.size();i++)
        {
            while(nums[i] != i+1)
            {
                int tmp = nums[i];
                if(nums[tmp-1] == tmp)
                    return tmp;
                swap(nums[i],nums[tmp-1]);
            }
        }
        
        return -1;
    }
};

合并区间：medium

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Solution {
public:

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>>res;
        if(intervals.size()==0 || intervals.size()==1)
            return intervals;
        sort(intervals.begin(),intervals.end(),[&,this](vector<int>&v1,vector<int>&v2)
        {return v1[0]<v2[0];});
        for(int i=0;i<intervals.size();i++)
        {
            vector<int>temp=intervals[i];
            while(i+1<intervals.size() && temp[1]>=intervals[i+1][0])//循环
            {
                ++i;
                temp[1]=max(temp[1],intervals[i][1]);
            }
            res.push_back(temp);
        }

        return res;
    }
};

下一个排列：medium

LeetCode中文

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

此题需要找出规律，举一个例子来说明，有如下的一个数组

1　　2　　7　　4　　3　　1

下一个排列为：

1　　3　　1　　2　　4　　7

那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后我们再以这个2的位置的后一个位置开始，从前往后找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字（不包括3的位置）反转一下即可，步骤如下：

1　　2　　7　　4　　3　　1

1　　2　　7　　4　　3　　1

1　　3　　7　　4　　2　　1

1　　3　　1　　2　　4　　7

再举几个例子验证仍然符合这个规律。因此，处理过程可总结以下几个步骤：

从后往前遍历数组，找到数值开始减小的那个位置idx，即nums[idx-1] < nums[idx]；
令idx_l = idx-1，从idx位置从前往后移动直到找到最后一个数值大于nums[idx_l]的元素；
交换nums[idx_l]和nums[idx]的值；
反转数组在idx位置之后的所有元素。

最后，就可以得到下一个排列。

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        if(len <= 0)
            return;
        
        int idx = len - 1;
        for(;idx >= 1 && nums[idx-1] >= nums[idx];idx--);
        
        if(idx == 0)
        {
            reverse(nums.begin(),nums.end());
            return;
        }
        
        int idx_l = idx - 1;
        for(int i=idx;idx<len;idx++)
        {
            if(nums[idx] <= nums[idx_l])
                break;
        }
        
        swap(nums[idx-1],nums[idx_l]);
        
        reverse(nums.begin() + idx_l + 1,nums.end());
        
        return;
    }
};

缺失的第一个正数：hard

41.缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

方法1

使用unordered_set结构的集合st装入nums中的元素，同时找到nums元素的最大值Max，然后遍历1~Max范围内的数，找到第一个不在集合st中数就是缺失的第一个正数，如果都在集合st中，那么缺失的第一个正数就在1和Max+1的较小值中取得。

时间复杂度：O(n)
空间复杂度：O(n)

C++代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> st;
        int Max = INT_MIN;
        for(auto a : nums)
        {
            st.insert(a);
            Max = max(Max,a);
        }
        
        for(int i=1;i<=Max;i++)
        {
            if(st.count(i) == 0)
                return i;
        }
        
        return max(Max + 1,1);
    }
};

方法2：优化空间复杂度

对于大小为n（n>0）的数组，这n个数可以分为以下几种情况：

这n个数都小于等于0
这n个数都大于n
存在一个或多个位于[1,n]的数

对于情况1和情况2，要查找的第一个缺失的正数就是1；

问题是对于情况3应该怎么考虑呢？

假设这些位于[1,n]的数i，在数组中的位置应该为i-1，而小于等于0的数，以及大于n的数，在数组剩余位置：

如果数组所有的数都在[1,n]，那么每个元素都在其值减1的位置，此时要找的第一个缺失的整数就是n+1；
否则，数组中，必然存在一个位置idx，其元素值不等于idx+1，而范围[1,n]就是正数序列最开始的n个数，因此，从左往右查找第一个下标加1不等于值的位置，那么要找的第一个缺失的正数就是该位置的下标加1。

注意：交换元素的方法可以将范围在[1,n]的元素放置到正确的位置,详见寻找重复数

时间复杂度：O(n)
空间复杂度：O(1)

C++代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        if(len == 0) return 1;
        
        for(int i=0;i<len;i++)
        {
            while(nums[i] > 0 && nums[i] <= len && nums[i] != i+1 && nums[nums[i] - 1] != nums[i])
            {
                swap(nums[nums[i] - 1],nums[i]);
            }
        }
        
        for(int i=0;i<len;i++)
        {
            if(nums[i] != i + 1)
                return i + 1;
        }
        
        return len + 1;
    }
};

数组总结

文章目录

哈希

两数之和:easy

两个数组的交集:easy

两个数组的交集II:easy

存在重复元素:easy

求众数:easy

有效的数独:medium

双指针

三数之和:medium

最接近的三数之和:medium

四数之和:medium

删除排序数组中的重复项：easy

移动零：easy

判断子序列:medium

盛最多水的容器：medium

合并两个有序数组：easy

找规律

螺旋矩阵：medium

螺旋矩阵II：medium

旋转图像：medium

矩阵置零：medium

除自身以外数组的乘积：medium

搜索二维矩阵：medium，二分查找

其它

杨辉三角：easy

缺失数字：easy

旋转数组：easy

寻找重复数：medium

合并区间：medium

下一个排列：medium

缺失的第一个正数：hard

Java关键字final、static使用总结

Java中遍历Map的多种方法示例及优缺点总结

Android编程计算函数时间戳的相关方法总结

Android EventBus 3.0.0 使用总结(必看篇)

数据算法使给定的一个二维数组(3×3)转置

js对象排序有几种方法（js中对象数组排序的方法）

遍历json数组对象（jquery遍历json数组了解）

谷歌浏览器无法登陆谷歌账户（总结这11个故障和对应解决方案）

php生成数组的使用示例 php全组合算法

js的数组有哪些常用方法（超详细的 JS 数组方法）