您现在的位置是：首页 >技术交流 >代码随想录day1 leetcode704，35，34，69，27，26网站首页技术交流

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

需要两点注意的是

• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

使用C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

数组的元素是不能删的，只能覆盖。

二维数组在内存的空间地址是连续的么？

不同编程语言的内存管理是不一样的，以C++为例，在C++中二维数组是连续分布的。

leetcode 704 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
//但是不能用right/2+left/2，因为如果左右都是奇数的话结果不正确
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

35.搜索插入位置

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

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = searchLeft(nums, target);
        int right = searchRight(nums, target);
        vector<int> res(2, -1);
        res[0] = left;
        res[1] = right;
        return res;
    }

    int searchLeft(vector<int>& nums, int target){
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target){
                r = mid - 1;
            }else if (nums[mid] < target){
                l = mid + 1;
            }else {
                if (mid == 0 || nums[mid - 1] != nums[mid]){
                    return mid;
                }else r = mid - 1;
            }
        }
        return -1;
    }

    int searchRight(vector<int>& nums, int target){
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target){
                r = mid - 1;
            }else if (nums[mid] < target){
                l = mid + 1;
            }else {
                if (mid == nums.size() - 1 || nums[mid + 1] != nums[mid]){
                    return mid;
                }else l = mid + 1;
            }
        }
        return -1;
    }
};

 69. x 的平方根 

class Solution {
public:
    int mySqrt(int x) {
        long l=0,r=x;
        while(l<=r){
            long mid=l+(r-l)/2;
            if(mid*mid==x){
                return mid;
            }else if(mid*mid>x){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return l-1;
    }
};

27. 移除元素

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

 26. 删除有序数组中的重复项

class Solution {
public:
//对比27题，自己定义val
    int removeDuplicates(vector<int>& nums) {
        int slow=0,fast=0;
        int val=10001;
        for(; fast < nums.size();fast++){
            if(fast>0) val=nums[fast-1];
            if(nums[fast]!=val){
                nums[slow++]=nums[fast];
            }
        }
        return slow;
    }
};