1、概念

數(shù)組是存放在連續(xù)空間上的相同類型的數(shù)據(jù)集合。
特點(diǎn)：
1、數(shù)組下標(biāo)都是從0開始的；
2、數(shù)組內(nèi)存空間的地址是連續(xù)的。

C++,要注意vector和array的區(qū)別，vector的底層實(shí)現(xiàn)是array，嚴(yán)格來講vector是容器，不是數(shù)組。
C++中二位數(shù)組在地址空間是連續(xù)的。測試代碼：

void test_arr() {
    int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

2、二分查找 主要理解區(qū)間定義，對循環(huán)條件的影響

特點(diǎn)：前提是有序數(shù)組，而且沒有無重復(fù)元素
題目：https://leetcode-cn.com/problems/binary-search/.
首位置 末尾位置，中間位置。
當(dāng)中間位置的數(shù)字>目標(biāo)數(shù)字 末尾位置挪移到中間位置
當(dāng)中間位置的數(shù)字<目標(biāo)數(shù)字 首位置挪移到中間位置
中間位置<0 中間位置>末尾位置 非法邊界。
第一種寫法 [left,right]
第二種寫法[left,right)

int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1; 

    while (left <= right){
        int middle = left + ((right - left) / 2); //防止溢出  防止什么溢出

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

    return -1;

}

2.1搜索插入位置（有序數(shù)組，要直接想到二分查找）

/*
題目：https://leetcode.cn/problems/search-insert-position/
給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值
不存在于數(shù)組中，返回它將會被按順序插入的位置。
特點(diǎn)：有序數(shù)組
解題思路：
1、用二分查找，查詢是否在數(shù)組中
2、若在返回索引
3、若不在，移動數(shù)組元素，把target插入數(shù)組中。從哪個索引開始移動數(shù)組元素，target插入
索引位置是哪？
*/
#include <stdio.h>

#define SIZE 4

int searchInsert(int* nums, int numsSize, int target);

int main()
{
    int nums[SIZE] = {1,3,5,6};
    int target = 0,targetIndex = 0;

    printf("請輸入你要查詢的數(shù)值：");
    scanf("%d", &target);

    targetIndex = searchInsert(nums,SIZE,target);

    if (targetIndex != -1)
    {
        printf("%d的索引是%d\n",target, targetIndex);
    }
    else
    {
        for (int i = 0; i < SIZE; i++)
        {
            printf("%d ",nums[i]);
        }
    }

}

int searchInsert(int* nums, int numsSize, int target)
{
    int left = 0,right = numsSize - 1;       //閉區(qū)間
    int middle = 0;

    while (left <= right)                    //循環(huán)條件是<開區(qū)間還是<= 為什么？<= 因為選擇的閉區(qū)間的寫法。若是選擇左閉右開的寫法 選擇<,并且保證循環(huán)過程中區(qū)間都是左閉右開。
    {
        middle = left + ((right - left) << 2);   //防止索引越界
        
        if (target < nums[middle])
        {
            right = middle -1;              //保持循環(huán)過程中是閉區(qū)間
        }
        else if (target > nums[middle])
        {
            left = middle + 1;              //保持循環(huán)過程中是閉區(qū)間
        }
        else
        {
            return middle;
        }
    }

    return left;        //為什么是left而不是middle。循環(huán)結(jié)束時，left的值滿足。
}

2.2 在排序數(shù)組中查找元素的第一個和最后一個位置

題目：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
解題思路：

2.3 x 的平方根

題目：https://leetcode.cn/problems/sqrtx/
解題思路：

2.4 有效的完全平方數(shù)

題目：https://leetcode.cn/problems/valid-perfect-square/
解題思路：

3、移除元素

題目：https://leetcode-cn.com/problems/remove-element/
第一種：暴力實(shí)現(xiàn)
第二種：雙指針：一個快指針，一個慢指針
快指針是尋找這個新數(shù)組里所需要的元素（除去所需要刪除目標(biāo)元素的元素）
新數(shù)組的更新的位置就是slow。
在快指針獲取到的值賦給慢指針就可以了。

int removeElement(int* nums, int numsSize, int val){
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; fastIndex++){
        if (val != nums[fastIndex]){
            nums[slowIndex++] = nums[fastIndex];
        }
    }

    return slowIndex;
};

類似題目：
26 刪除排序數(shù)組中的重復(fù)項
283 移動零
844 比較含退格的字符串

有序數(shù)組的平方

題目：https://leetcode-cn.com/problems/squares-of-a-sorted-array/
第一種方法：暴力解法 每個數(shù)平方之后，排序即可
第二種方法：雙指針法
考慮題目的特征：有序數(shù)組，那么數(shù)組的平方的最大值就在數(shù)組的兩端，不是最左邊就是最右邊，不可能是中間。
此時可以考慮雙指針法，i指向起始位置，j指向終止位置
定義一個新數(shù)組result，和A數(shù)組一樣的大小，讓k指向result數(shù)組終止位置。
怎么想到定義了一個新數(shù)組？因為數(shù)組的元素已經(jīng)改變，不僅是位置的改變還有內(nèi)容的改變。

#include <stdio.h>
#include <math.h>

int main()
{
    int originalArr[5] = {-3,-2,4,5,6};
    int newArr[5] = {0};
    int i = 0;
    int j = 4;
    int k = 4;

    /*
    首先比較初始元素的平方和末尾元素的平方大小
    其次，將較大的一方放入新數(shù)組的末尾位置，并移動i或j的位置。

    循環(huán)結(jié)束的條件，i <= j
    */
   while (i <= j)
   {
        if (pow(originalArr[i],2) > pow(originalArr[j],2))
        {
            newArr[k] = pow(originalArr[i],2); 
            i++;
            k--;
        }
        else
        {
            newArr[k] = pow(originalArr[j],2);
            j--;
            k--;
        }
   }

   for (int i = 0; i < 5; i++)
   {
        printf("%d ",newArr[i]);
   }
   

   return 0;

}

長度最小的子數(shù)組（滑動窗口）

螺旋矩陣

題目：https://leetcode-cn.com/problems/spiral-matrix-ii/文章來源地址http://www.zghlxwxcb.cn/news/detail-421304.html

總結(jié)

到了這里，關(guān)于數(shù)組的知識點(diǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！