【算法与数据结构】【数组篇】【题6-题10】

系列文章

本人系列文章-CSDN博客https://blog.csdn.net/handsomethefirst/article/details/138226266?spm=1001.2014.3001.5502

1.数组基本知识点

1.1概念

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

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

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

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

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

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

题6

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

作题思路：

1.第一步：找规律，我们发现其每次遍历输出的x+y坐标的和是相等的。且当和为偶数的时候，是x递减，y递增，而当和为奇数的时候，是x递增，y递减。

[0,0]                 0 偶数
[0,1],[1,0]         1 奇数
[2,0],[1,1],[0,2] 2 偶数
[1,2][2,1]          3 奇数
[2,2]                 4   偶数

2.第二步：查找遍历次数，不难发现其遍历的上限是m+n +1，此处m=M-1，n =N-1。

3.第三步：确定开始时，x位置和y的位置和结束时，x，y的位置。不难发现，

        当为偶数的时候，如果x+y=i，i的值小于最大的行数，代表坐标x从i开始，y从0开始，如果i大于等于最大的行数，代表坐标x从m开始，y=i-m开始。

        当为奇数的时候，如果x+y=i，i的值小于最大的列数，代表坐标y从i开始，x从0开始, 如果i大于等于最大的列数，代表坐标y从n开始，x=i-n开始

代码案例：

class Solution
{
public:
    vector<int> findDiagonalOrder(vector<vector<int>> &mat)
    {
        int m = mat.size() - 1;    // 横的长度
        int n = mat[0].size() - 1; // 竖的长度

        vector<int> returnvector;
        for (int i = 0; i < m + n + 1; i++)
        {
            if (i % 2 == 0) // 如果是偶数,其是向上遍历，因此其开始时候，x是大于y的，
            {
                int x = i < m ? i : m; // 如果i小于最大的行数，代表坐标x从i开始，y从0开始，如果i大于等于最大的行数，代表坐标x从m开始，y=i-m开始
                int y = i -x;

                while (x >= 0 && y <= n) // 注意x和y都不能越界
                {
                    returnvector.push_back(mat[x][y]);
                    x--;
                    y = i - x;
                }
            }
            else if (i % 2 == 1) // 如果是奇数，则是向下遍历
            {
                int y = i < n ? i : n; // 如果i小于最大的列数，代表坐标y从i开始，x从0开始, 如果i大于等于最大的列数，代表坐标y从n开始，x=i-n开始
                int x = i - y;

                while (x <= m && y >= 0) // 注意x和y都不能越界
                {

                    returnvector.push_back(mat[x][y]);
                    y--;
                    x = i - y;
                }
            }
        }
        return returnvector;
    }
};

题7

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

思路：

双指针：
双指针情形一：
指针向中间或两端移动，移动方向始终相对
双指针情形二：
指针向同侧移动，形成前后指针或快慢指针

第一步：定义两个指针，一个指向头位置，一个指向末尾位置。

第二步：交换元素。

第三步：移动头尾指针。

代码案例：

class Solution
{
public:
    void reverseString(vector<char> &s)
    {
        int stringsize = s.size();
        if (stringsize <= 0)
        {
            return;
        }

        int head = 0;
        int tail = stringsize - 1;
        while (head <tail)
        {
            swap(s[head],s[tail]);
            head ++;
            tail --;
        }
    }
};

题8

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该最大总和。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

思路：

要求 sum = a + b + c +...的最大值，那就每一个加数都尽量往大了取。首先考虑所有数的最大值，但是显然这个值不合要求，因为这里的每个加数都是通过min最小值得到的，最大值没有比它更大的，无法实现。那就考所有元素中虑第二大的值，第二大的值如果要作为min值被选出，那就必须得和最大值在一个组。这也是所有加数所能取得到的最大值。
最大值和次大值被选在一个组，剩下的元素中又会有新的最大值和次大值。依次类推。

代码案例：

class Solution
{
public:
    int arrayPairSum(vector<int> &nums)
    {
        int arraysize = nums.size();
        sort(nums.begin(), nums.end());

        int sum = 0;

        for (int i = 0; i < arraysize; i = i + 2)
        {
            sum += nums[i];
        }

        return sum;
    }
};

题9

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。
如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3]

思路：

需要找到两个符合要求的值，优先双指针。

首先，是一个递增排序，那么我们可以知道头尾相加，判断最大值和最小值的和是否等于目标值，如果大于目标值，则说明我们值找大了，那就要找到次第二最大值，作为新区间的最大值，然后继续判断是否等于目标值。

如果是小于目标值，则说明我们值找小了，因此需要找到次第二最小值，作为新区间的最小值，然后继续判断是否等于目标值。

当等于的时候，则输出值。

代码案例

class Solution
{
public:
    vector<int> twoSum(vector<int> &numbers, int target)
    {
        int first = 0; 
        int tail = numbers.size() - 1;
        vector<int> returnvector;
        while (first < tail) 
        {

            if ((numbers[first] + numbers[tail]) == target) //首部尾部相加等于目标值，返回结果集
            {
                returnvector.push_back(first + 1);
                returnvector.push_back(tail + 1);
                return returnvector;
            }
            else if ((numbers[first] + numbers[tail]) > target)//首部尾部相加大于目标值，则说明尾部前移，值才能变小
            {
                tail--;
            }
            else if ((numbers[first] + numbers[tail]) < target)//首部尾部相加小于目标值，则首部后移，值才能变大
            {
                first++;
            }
        }
        return returnvector;
    }
};

题10

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）

思路：

运用双指针的快慢指针，只有快指针不等于目标值的时候，才将快指针指向的值赋值给慢指针指向的值。这样慢指针指向的值就全都是去除了目标值的值。

代码案例：

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int slow = 0;
        int numsize = nums.size();

        for (int fast = 0; fast < numsize; fast++)
        {

            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
        }

        return slow;
    }
};