Leetcode array 数组题目解题报告

作者: BookThief | 来源:发表于2018-07-20 15:24 被阅读0次

1. Remove Duplicates from Sorted Array

Description： Easy

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.

Analysis

a. 数组前提是有序的，从一个数组中去掉重复元素后，返回这个数组的长度。

b. 不能利用其它多余空间。

Solution 1：双游标法

code and annotation

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 首先考虑两种最简单的情况，数组大小为0和1，这两种情况都可以直接返回结果
        // 这两种情况返回值正好是数组大小，下面这行代码正好表达了这个过程
        if(nums.size()<=1)
            return nums.size();
        else
        {
            // index_new指针记录当前发现的不重复的元素的‘数量’
            // 并且这个索引指向的值是最新的不重复元素的值
            int index_new = 0
            // each指针开始从第二个元素遍历数组剩余元素
            for(int each = 1; each<nums.size(); each++)
            {
              // 遍历过程中发现新的元素，开始更新
              if(nums[index_new] != nums[each])
              {
                // 更新已发现的不重复元素数量
                index_new++;
                // 更新最新的不重复元素值
                nums[index_new] = nums[each];
              }
            }
            // 注意index_new是从0开始的，当有两个不重复元素，index_new为1，所以最后结果还要加1
            return index_new + 1;
        }
    }
};

tips

实际是双游标法，一个负责遍历，一个负责记录。
利用两个指针，一个指针记录当前发现的不重复的元素的‘数量’，并且这个索引指向的值是最新的不重复元素的值。初始位置为0。
另一个指针遍历数组的每一个元素。初始位置为1。
遍历数组时记得 <nums.size(), 没有等号。数组大小是数组最大索引加1。
遍历指针更新就是不断加1，数量指针的更新是关键（发现新元素）。

Solution 2：利用STL

code and annotation

class Solution {
public:
    int removeDuplicates(vector<int>& nums){
        // 利用unique函数, 返回一个迭代器指针（去重后的尾地址）
        auto iLocator = unique(nums.begin(), nums.end());
        // distance函数计算元素偏移量
        return distance(nums.begin(), iLocator);
    }
};

tips

unique接收两个迭代器，作用是“去掉”容器中相邻元素的重复元素（不一定要求数组有序），它会把重复的元素添加到容器末尾（所以数组大小并没有改变），而返回值是去重之后的尾地址。（这个尾地址是最后一个未重复的后一个位置）
distance也是接收两个迭代器，计算两者的偏移量。

2. Remove Duplicates from Sorted Array Ⅱ

Description： Medium

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Given nums = [1,1,1,2,2,3],
Your function should return length = 5

Analysis

a. 这道题跟Remove Duplicates from Sorted Array比较类似，区别只是这里元素可以重复出现至多两次，而不是一次。其实也比较简单，只需要维护一个counter，当counter是2时，就直接跳过即可，否则说明元素出现次数没有超，继续放入计数的指针，若遇到新元素则重置counter。

b. 但其实这里的前提是数组已经有序，其实如果遍历指针i扫到的当前元素在index之前已经存在两个（注意，由于A是排好序的，因此只需要判断前两个就行），那么i继续前进。否则将i指向的元素加入index，index与i一起前进。

Solution 1

code and annotation

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        // 注意最简单的情况是数组大小0，1，2
        if(n<=2)
            return n;
        else
        {
            // 记录指针和遍历指针初始都是2
            int index_new = 2;
            for(int i = 2; i<n; i++){
                if(nums[i] ! = nums[index_new])
                {
                    nums[index_new] = nums[i];
                    index_new++;
                }
            }
            return index_new;
        }
    }
};

tips

不同之处是两种指针的初始值设置；
记录指针的更新策略其实也是一样的。

3. Search in Rotated Sorted Array

Description： Medium

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

analysis

a. 一个有序（升）的数组进行旋转。并且这个旋转的中心点也不确定，再在这个数组里寻找某个元素的位置。
b. 没有重复元素
c. 任取一个位置，其左右两边必有一边是有序的。那么在这个有序表里查找某个元素就可以使用二分法。

Solution

code and annotation

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 线性表搜索问题一般都会用到二分法
        // 二分法涉及三个指针min max mid
        int min = 0, max = nums.size()-1, mid = 0;
        // 二分法最终的停止条件
        while(min <= max){
            // 初始第一次二分的mid
             int mid = (min+max)/2;
             // 如果mid恰好是target(最终target都会到mid这里)
             if(nums[mid] == target)    return mid;
             // 如果左半部分有序,则在此半部分（有序字符串）进行二分查找
             if(nums[min] <= nums[mid]){
                 if(nums[min]<=target && target<nums[mid])
                    max = mid - 1;
                else
                    min = mid + 1;
             }
             // 如果右半部分有序
             else{
                 if(nums[mid]< target && target<=nums[max])
                    min = mid + 1;
                else
                    max = mid - 1;
             }
        }
        // 不满足最高二分条件min<=max时
        return -1;
    }
};

tips

在旋转数组里搜索元素，看起来有点麻烦，其实理清了比较简单。仍然采用切一半二分。但是由于是有序旋转的，所以切一半会有问题。所以需要进一步判断。
假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：

（1）如果target==A[m]，那么m就是我们要的结果，直接返回；

（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。

（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。

二分法大体框架

vector<int> N; int target
int left = 0;
int right = size-1;
int mid = 0;
while(left <= right)
{
    mid = (left + right)/2;
    if(N[mid] == target)
        return mid;
    if(N[left] <= target && target < N[mid])
        right = mid - 1;
    else
        left = mid + 1;
}

// 二分法前提是用在有序数组，并且要注意二分法的停止条件以及大体框架
// 二分法最终return的都是mid
// 注意几次等号边界，target和mid的第一处if等号，其余都不等

4. Search in Rotated Sorted Array II

Description： Medium

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Analysis

a. 和之前一条题目相比仅仅是多了重复元素的限制
b. 之前没有重复元素，判断左边还是右边有序，只需考虑nums[left]<=nums[mid]，这里取等号，是因为我们知道没有重复元素。
c. 有了重复元素，只需把上面一个判断分成两步即可，当nums[left]=num[mid]时，跳过该重复元素。

Solution

code and annotation

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

tips

有序表查找需要熟记二分法
code中打*号的else，去掉代码即失效。

5. Median of Two Sorted Arrays

Description： Hard

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

Analysis

a. 两个有序的数组，找到合并后的数组中中间的值。
b. 这个题目可以转换为一个更普适的版本，给定两个已经排好序的数组，找到两者所有元素中第k大的元素。

c. O(m+n)的解法比较直观，直接合并两个数组后排序，再找到第k大的元素。但是不符合本题的复杂度要求。

d. 另一种思路，其实，我们求第k大的元素，是不需要“排序”这么复杂的操作的。我们可以设立一个计数器count记录当前找到的第k大的元素，同时设立两个指针，PA， PB，分别指向A,和B两个数组的第一个元素。如果此时*PA较小，则PA++, count++。等count==k时，我们就找到了那个元素。O(k)的时间，O(1)的空间。但是k接近m+n时，还是O(m+n)。

e. 还有什么好的思路吗？我们删除在k之前的元素必须一个个找吗？假如我们删除一半一半呢，我们要充分利用有序这一个特点。类似于二分法。

Solution

code and annotation

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int total = m + n;
        // 判断总数奇偶，奇数直接去中间数，偶数求两个值取平均
        // total是数量，注意中间值的索引。
        if(total & 0x1)
            return find_kth(nums1.begin(), m, nums2.begin(), n, total/2);
        else
            return (find_kth(nums1.begin(), m, nums2.begin(), n, total/2)
            + find_kth(nums1.begin(), m, nums2.begin(), n, total/2 - 1))/2.0;
private:
    // 定义找到第k个数的递归函数，A,B是两个迭代器
    static int find_kth(auto A, int m, auto B, int n, int k)
        {
            // 保证输入的第一个数组要比第二个大，这样可以简化后面的代码
            if(m < n)
                return find_kth(B, n, A, m, k);
            // 递归停止条件
            // 至少有一个数组大小为0，因为m较小，只讨论m
            if(m == 0)
                return *(B + k - 1);
            if(k == 1)
                return min(*A, *B);
            // 保证ia+ib = k
            // 注意此时 ia ib仍然是数量，注意算索引要减一；
            int ia = min(m, k/2);
            int ib = k - ia;
            // 开始对ia ib进行三种判断，分别对应三种情况
            if(*(A + ia -1) < *(B + ib - 1))
                return find_kth(A+ia-1+1, m-ia, B, n, k-ia);
            else if(*(A + ia -1) > *(B + ib - 1))
                return find_kth(A, m, B+ib-1+1, n-ib, k-ib);
            else
                // 想一想，恰恰是相等的情况让我们能够理解为什么这么做。
                return *(A + ia - 1);
        }
    }
};

tips

核心思想：每个数组取k/2（较小数组小于k/2时，取m，保证两者取的加起来为k），当A[k/2 - 1]==B[k/2 - 1]时，第k大的值恰好是该相等值。这就促使我们分析另两种情况，A[k/2 - 1]<B[k/2 - 1]时，A[0]到A[k/2 -1]一定不是k大元素且比k小，那么我们就可以删掉A数组的这些元素，变成A'。之后继续在A’和B上找第k-k/2大的元素。
递归函数一定要注意递归停止条件，return的是确定的值，而不是递归函数本身就是停止条件。
auto A --> std::vector<int>::const_iterator A

6. Longest Consecutive Sequence

Description： Hard

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Analysis

a. 找到数组中连续的最长子数组的长度。
b. O(nlogn)的话可以先排序，但是这里不行。
c. 需要注意的是不能重复考虑。比如上面例子，1，2，3，4是最长连续数组，考虑过4后，就不能再去单独考虑1，3，2。
d. 我们可以建立一个哈希映射，记录每一个数是否被考虑过。再对每一个元素进行左右扩张，查找最大长度。

Solution

code and annotation

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> used;
        // 哈希表每个key为nums元素，value初始为false，初始每个元素没有考虑过。
        for(auto i : nums)
            used[i] = false;
        // 遍历每一个元素
        int longest = 0;
        for(int i=0; i<nums.size(); i++)
        {
            // 如果发现这个元素被考虑过了，跳过该元素。
            if(used[nums[i]])
                continue;
            // 否则先把该元素设为考虑过了
            int length = 1;
            used[nums[i]] = true;
            // 以该元素在连续表上向右扩张
            for(int j = nums[i] + 1; used.find(j)!=used.end(); j++)
            {
                // 更新长度
                length += 1;
                // 并且把延伸的元素设为已考虑
                used[j] = true;
            }
            // 以该元素在连续表上向右扩张
            for(int j = nums[i] - 1; used.find(j)!=used.end(); j--)
            {
                // 更新长度
                length += 1;
                // 并且把延伸的元素设为已考虑
                used[j] = true;
            }
            // 考虑过一个未考虑的元素，更新最大长度
            longest = max(longest, length);
        }
        return longest;
    }
};

tips

将vector映射到map是一种经常使用的策略。map的find函数可以帮助
时间复杂度要求我们不能先对数组排好序。
find函数如果找不到元素，返回end
使用哈希表监控每一个元素是否被使用过，可以大幅度减少算法复杂度。

7. Two Sum

Description： Easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Analysis

a. 给一个值，找出数组里相加和为该值的索引。

b. 遍历每一个元素，计算gap，再找gap。思想很简单，但是找元素，以及建立索引和值的对应。显然用哈希表

Solution

code and annotation

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 建立值-索引的map
        unordered_map<int, int> value_index;
        // 建立最终返回结果的vector
        vector<int> result;
        // vector到map 值-索引
        for(int i = 0; i<nums.size(); i++)
            value_index[nums[i]] = i;
        for(int i = 0; i<nums.size(); i++)
        {
            int gap = target - nums[i];
            // map是值-索引还是索引-值，取决于map的find函数是找key。
            if(value_index.find(gap)!=value_index.end() && 
            value_index[gap] != i){
                result.push_back(i);
                result.push_back(value_index[gap]);
                // 只需找到一对
                break;
            }
        }
        return result;
    }
};

tips

vector到map的映射，6，7题都有很好的表现
map find的是key，由此设计map

8. Remove Element

Description： Easy

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

Analysis

a. 删除掉一个数组内所有指定的元素，然后返回数组长度

b. 其实本题看起来有很简单的思路，用一个数组，遍历给定的数组，如果遍历的元素不是target就加入建立的新数组。但是这样空间复杂度很高。

c. 存在一个空间复杂度为1的方法，就是利用双游标，只在原数组上进行覆盖。（类似链表删除的操作）

Solution 1: 双游标

code and annotation

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 相当于新数组的游标
        int index = 0;
        // 遍历
        for(int i = 0; i<nums.size(); i++)
        {
            if(nums[i] != val)
            {
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
};

Solution 2: STL

code and annotation

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        return distance(nums.begin(), remove(nums.begin(), nums.end(), val));
    }
};

tips

distance接收两个迭代器，计算两者偏移量
remove()函数接收两个迭代器和一个元素，返回去掉这个元素后的最后一个迭代器。
熟悉STL函数可以方便解题。

9. Rotate image

Description： Medium

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

Analysis

a. 将一个n*n的矩阵旋转90度，并且不能使用另外的空间，只能在原始矩阵上进行操作

b. 最简单的思路是从外到内一圈圈旋转，但这种方法比较慢。

c. 从观察角度会发现，旋转90度可以拆分为首先沿着水平中线翻转一次，然后再沿着主对角线翻转一次。而这两个操作实现比较容易

Solution

code and annotation

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();
        # 先水平翻转
        for(int i = 0; i<n/2; ++i)
            for(int j = 0; j<n; ++j)
                swap(matrix[i][j], matrix[n-1-i][j]);
        
        # 再沿着主对角线翻转
        for(int i = 0; i<n; ++i)
            for(int j =i+1; j<n; ++j)
                swap(matrix[i][j], matrix[j][i]);
    }
};

tips

分解思想：旋转90度可以分解为两个简单操作
索引的边界可以画图一步步获得。

10. Plus One

Description： Medium

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Analysis

a. 实际上就是一次加法的模拟，这里的加数是1，其实可以拓展为通用的加数（0到9）

b. 从最后一位数字开始一直加到最后一位----更新当前被加数字----更新进位: 与10的除数----再次更新当前被加值：与10的余数。

Solution

code and annotation

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        add(digits, 1);
        return digits;  
    }
private:
    // 0<=plusnumber<10
    void add(vector<int>& digits, int plusnumber){
        // 最后加的数字可以看成第一次的进位
        int c = plusnumber;
        // 从最后一位数字开始一直加到最后一位
        for(auto it = digits.rbegin(); it!=digits.rend(); ++it)
        {
            // 更新当前被加数字
            *it += c;
            // 更新进位: 与10的除数
            c = *it/10;
            // 再次更新当前被加值：与10的余数
            *it %= 10;
        }
        // 如果计算完所有数值，进位还不是0，说明位数需要增加
        if(c!=0)
            digits.insert(digits.begin(), 1);
    }
};

tips

c.begin() 返回一个迭代器，它指向容器c的第一个元素

c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置

c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素

c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置

11. Climbing Stairs

Description： Medium

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Analysis

a. 很有趣的一条题目，如果有n个阶梯，你每次可以走一级或两级，问一共有多少种走法？

1.假设当有n个台阶时假设有f(n)种走法。

2.青蛙最后一步要么跨1个台阶要么跨2个台阶。

3.当最后一步跨1个台阶时即之前有n-1个台阶，根据1的假设即n-1个台阶有f(n-1)种走法。

4.当最后一步跨2个台阶时即之前有n-2个台阶，根据1的假设即n-2个台阶有f(n-2 )种走法。

5.显然n个台阶的走法等于前两种情况的走法之和即f(n)=f(n-1)+f(n-2)。

c. 本质上是一个斐波那契数列

Solution

code and annotation

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2)
            return n;
        else
        {
            int first = 1, second = 2, third = 0;
            for(int i = 3; i<=n; ++i)
            {
                third = first + second;
                first = second;
                second = third;
            }
            return third;
        }
        
    }
};

12 Set Matrix Zeroes

Decription：easy

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Analysis

一个m*n的矩阵，如果有一个元素为0，则将其一行和一列的数字都变为0；
这是一个很有趣的题目，对复杂度考察很到位。
最大的问题就是我们遇到0的时候不能直接把矩阵的行列在当前矩阵直接置0，否则后面还没访问到的会被当成原来是0，最后会把很多不该置0的行列都置0了。
一个直接的想法是备份一个矩阵，然后在备份矩阵上判断，在原矩阵上置0，这样当然是可以的，不过空间复杂度是O(m*n)，判断和置零分开坐。
5.判断某一项是不是0只要看它对应的行或者列应不应该置0就可以，所以我们可以维护一个行和列的布尔数组，然后扫描一遍矩阵记录那一行或者列是不是应该置0即可，这种方法的空间复杂度是O(m+n)。
还有什么方法可以进一步降低复杂度呢，我们考虑使用第一行和第一列来记录上面所说的行和列的置0情况，这里问题是那么第一行和第一列自己怎么办？想要记录它们自己是否要置0，只需要两个变量（一个是第一行，一个是第一列）就可以了。然后就是第一行和第一列，如果要置0，就把它的值赋成0（反正它最终也该是0，无论第一行或者第一列有没有0），否则保留原值。然后根据第一行和第一列的记录对其他元素进行置0。最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。这样的做法只需要两个额外变量，所以空间复杂度是O(1)。

Solution1 O(m+n)

class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
  const size_t m = matrix.size();
  const size_t n = matrix[0].size();
  vector<bool> row(m, false); // 标记该行是否存在0
  vector<bool> col(n, false); // 标记该列是否存在0
  for (size_t i = 0; i < m; ++i) {
    for (size_t j = 0; j < n; ++j) {
      if (matrix[i][j] == 0) {
        row[i] = col[j] = true;
        }
      }
    }
  for (size_t i = 0; i < m; ++i) {
    if (row[i])
      fill(&matrix[i][0], &matrix[i][0] + n, 0);
    }
  for (size_t j = 0; j < n; ++j) {
    if (col[j]) {
      for (size_t i = 0; i < m; ++i) {
        matrix[i][j] = 0;
      }
    }
  }
  }
};

Solution2 O(1)

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        
        int m=matrix.size();
        int n=matrix[0].size();
        bool row0=false;//标记第一行是否存在0
        bool column0=false;//标记第一列是否存在0
        
        if(m==0||n==0)return;//特殊情况处理
        for(int i=0;i<m;i++)
        {
            if(matrix[i][0]==0)column0=true;//第一列存在0
        }
        
        for(int i=0;i<n;i++)
        {
            if(matrix[0][i]==0)row0=true;//第一行存在0
        }
        
        for(int i=1;i<m;i++)//遍历除第一行和第一列以外的行列
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[0][j]=0;//存储0元素出现的列下标
                    matrix[i][0]=0;//存储0元素出现的行下标
                }
            }
        }
        
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                if(matrix[0][j]==0||matrix[i][0]==0)//对应行列全部置零
                matrix[i][j]=0;
            }
        }
        if(row0==true)//如果第一行存在零，第一行置零
        {
            for(int i=0;i<n;i++)
            matrix[0][i]=0;
        }
        if(column0==true)//如果第一列原始存在0，则第一列置零
        {
            for(int i=0;i<m;i++)
            matrix[i][0]=0;
        }
        
    }
};

Leetcode array 数组题目解题报告

1. Remove Duplicates from Sorted Array

Description： Easy

Analysis

Solution 1：双游标法

Solution 2：利用STL

2. Remove Duplicates from Sorted Array Ⅱ

Description： Medium

Analysis

Solution 1

3. Search in Rotated Sorted Array

Description： Medium

analysis

Solution

4. Search in Rotated Sorted Array II

Description： Medium

Analysis

Solution

5. Median of Two Sorted Arrays

Description： Hard

Analysis

Solution

6. Longest Consecutive Sequence

Description： Hard

Analysis

Solution

7. Two Sum

Description： Easy

Analysis

Solution

8. Remove Element

Description： Easy

Analysis

Solution 1: 双游标

Solution 2: STL

9. Rotate image

Description： Medium

Analysis

Solution

10. Plus One

Description： Medium

Analysis

Solution

11. Climbing Stairs

Description： Medium

Analysis

Solution

12 Set Matrix Zeroes

Decription：easy

Analysis

Solution1 O(m+n)

Solution2 O(1)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读