数组理论基础

• 数组是存放在连续空间上的相同类型数据的集合
• 数组的元素是不能删的，只能覆盖

704.二分查找

LeetCode：704.有序数组的平方

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
           int length = nums.size();

        int i = 0, j = length - 1;
       
        while (i <= j)
        {
            //左闭右闭
             
            int mid = (i + j) / 2;

            if (target < nums[mid])//左区间
            {
                j = mid - 1;
            }
            else if(target>nums[mid])//右区间
            {
                i = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;//未找到
    }
};

27.移除元素

LeetCode：27.移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        //双指针法：快慢指针
        int slow=0, fast = 0;
        for (fast; fast < nums.size(); fast++)
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

977.有序数组的平方

LeetCode：977.有序数组的平方

暴力法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums)
    {

		for(int i=0;i<nums.size();i++)
        {
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());

        return nums;

    }
};

双指针法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

// 双指针法
        int l = nums.size() - 1;
        vector<int> result(nums.size(), 0);
        int i = 0, j = l;
        while (i <= j)
        {
            if (nums[i] * nums[i] < nums[j] * nums[j])
            {
                result[l] = nums[j] * nums[j];
                l--;
                j--;

            }
            else
            {
                result[l] = nums[i] * nums[i];
                l--;
                i++;
            }
        }
        return result;
    }
};