【算法与数据结构】【数组篇】【题1-题5】

1.数组基本知识点

1.1概念

数组就是一个集合。数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引，快速访问数组中的元素。

数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。

1.2 相关操作的时间复杂度和空间复杂度

访问元素时间复杂度都是O(1)，空间复杂度O(1)，因为对于固定大小的数组，访问时间不随数组大小而变化。通过下标可直接访问。

修改元素：时间复杂度O(1)，空间复杂度O(1)，与n无关，通过下标可直接修改

插入元素和删除元素：时间复杂度O(1)，空间复杂度O(1)，插入和删除元素都需要移动后面的元素，因此随n变化。

题1：寻找数组的中心索引

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

解答思路：

第一步：先用for循环求总和
第二步：当位置为i时，找到其左边所有元素的合。
第三步：然后用总和减去其左边所有元素的合再减去当前元素的值。就是右边元素的值。
第四步：判断其左边元素和和右边元素和是否相等。
第五步：如果相等，则返回i，如果不相等，循环判断下一个元素。
第六步：如果最后一个元素仍然不满足，返回-1

代码案例：

class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        int size = nums.size();
        if (size <= 0)
        {
            return 0;
        }

        int sum = 0;

        for (int &i : nums)
        {
            sum = sum + i; //第一步：先用for循环求总和
        }

        int leftsum = 0;

        for (int i = 0; i < size; i++)
        {

            if (leftsum == (sum -leftsum - nums[i]))//第二步和第三步和第四步
            {
                return i; //第五步
            }

            leftsum += nums[i];//第五步
        }

        return -1;//第六步
    }
};

题2：搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

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

示例 2:

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

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

 解题思路：

思路：
第一步：此处特定说明了必须使用时间复杂度为 O(log n) 的算法。所以采用二分查找法。首先二分算法适用于已经排序过的数组。
第二步：二分法需要每次找到中间值，因此需要定义left，right，middle三个变量。
第三步：left=0，right = nums.size() - 1; middle = left + (right - left) / 2;
第四步：通过while循环进行查找
第五步：如果目标值刚好等于中间值，即target = nums[middle],则return middle；
第六步：如果目标值大于中间值，则说明其应该在右区间，因此需要挪动左边界值（left）为middle+1。
        如果目标值小于中间值，则说明其应该在左区间，因此需要挪动右边界值（right）为middle-1。
第七步：如果最后左边界和右边界相等，此时会退出whlie循环，此时说明区间只有一个值了，判断其是否等于此值，如果大于等于则return left+1；就是新插入的位置。
        如果此时目标值小于此值，则返回left的位置，要插入当前这个值的位置。

代码案例：

class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        if (nums.size() <= 0)
        {
            return -1;
        }

        int left = 0;
        int right = nums.size() - 1;
        int middle = left + (right - left) / 2;
        while (left < right)
        {
            middle = left + (right - left) / 2;
            if (target == nums[middle])
            {
                return middle;
            }
            else if (target < nums[middle])
            {
                right = middle - 1;
            }
            else if (target > nums[middle])
            {
                left = middle + 1;
            }
        }

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

 题3：合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

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

示例 2：

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

解题思路：

思路：

一般需要后一个比前一个小的题，首先先思考排序

第一步：排序，确保第一个start小于第二个start
第二步：如果intervals[i].end >= intervals[i+1].start，则将其组合，选择两个end值中最大的那个
        如果intervals[i].end < intervals[i+1].start，则无法合并，然后循环查找下一个区间和上一个区间再次进行循环对比

代码案例：

class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {

        if (intervals.size() == 1)
        {
            return intervals;
        }

        sort(intervals.begin(), intervals.end()); // 第一步：排序，确保第一个start小于第二个start

        vector<vector<int>> returnvector;
        returnvector.push_back(intervals[0]);//第二步：先放入第一个值，以此为判断
        int j = 0;

        for (int i = 1; i < intervals.size(); i++)
        {
            if (returnvector[j][1] >= intervals[i][0])//第三步：如果第一个值的end大于第二个值的start，则合并
            {

                returnvector[j][1] = max(returnvector[j][1], intervals[i][1]);//选择第一个值的end和第二个值end中最大的那个
            }
            else //否则，说明没有公共区间，则放入第二个
            {
                returnvector.push_back(intervals[i]);//只有合并完成，才会往后判断，否则一直基于此子数组进行合并
                j++;
            }
        }

        return returnvector;
    }
};

题4：旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 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();
        // 第一步：先对角线反转
        for (int i = 0; i < N; i++)
        {
            for (int j = i; j < N; j++)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 第二步：水平翻转
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N / 2; j++)
            {
                swap(matrix[i][j], matrix[i][N - 1 - j]);
            }
        }
    }
};

题5：零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

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

思路：

第一步：遍历二维数组，找出为0的x下标和y下标，并保存起来。

第二步：然后两次循环将其他位置清0

代码案例：

class Solution
{
public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int M = matrix.size();
        int N = matrix[0].size();

        vector<int> x;
        vector<int> y;

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (matrix[i][j] == 0)
                {
                    x.push_back(i);
                    y.push_back(j);
                }
            }
        }

        for (auto &i : x)
        {
            for (int j = 0; j < N; j++)
            {
                matrix[i][j] = 0;
            }
        }

        for (auto &i : y)
        {
            for (int row = 0; row < M; row++)
            {
                matrix[row][i] = 0;
            }
        }
    }
};