【Day1】数组、704二分查找、27移除元素-创新互联

【Day1】数组、704二分查找、27移除元素

• 数组
• 704 二分查找
• • 版本一 左闭右闭 即[left, right]
  • 版本二 左闭右开 即[left, right)
• 27 移除元素
• • 暴力解法
  • 双指针法

练习的题目来自力扣，顺序按照代码随想录进行。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、网页空间、营销软件、网站建设、仙桃网站维护、网站推广。数组

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

• 数组的下标都是从0开始的
• 数组内存空间的地址是连续的（一维、二维都是连续的）
• 数组的元素是不能删的，只能覆盖
• 数组是随机存取的存储结构

如果使用C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
vector是顺序容器，其利用连续的内存空间来存储元素，但是其内存空间大小是能够改变的。
array是顺序容器，其也是利用连续的内存空间来存储元素，但它的内存空间是固定大小的，申请之后就无法改变。

704 二分查找

二分查找的前提是数组是有序数组，且数组中无重复元素。

因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

题目链接：704 二分查找

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

版本一 左闭右闭 即[left, right]

[left, right] 左右两边都能取到，nums[m]不可能等于target，所以nums[m]>target，则right=m-1

// 版本一 左闭右闭即[left, right]
class Solution {public:
    int search(vector& nums, int target) {//vector好比是一个数组
        int left=0;
        int right=nums.size()-1;    //左闭右闭，下标从0开始，最后一个数就是个数减1
        while (left<=right)
        {int middle=left+((right-left)/2);  //防止溢出，等价于 (left+right)/2
            if(nums[middle]>target){right=middle-1;//target在左区间， middle是几个数值的中间数 数组这里是以下标看来值，因此下标-1
            }else if(nums[middle]left=middle+1;//target在右区间
            }else{  //nums[middle]==target
                return middle;
            }
        }
        // 未找到目标值
        return -1;
    }
};

关于下面这句代码

int middle = left + ((right - left) / 2);  //而不用mid = （left+right）/2

原因：mid = (left + right) / 2 容易溢出！因为left+right很容易超过int范围！而mid = left + (right - left) / 2 不容易溢出，所以建议以后写二分时要用mid = left + (right - left) / 2
来源：二分查找

版本二 左闭右开 即[left, right)

[left, right） 左边值能取到右边值取不到，nums[m]可能等于target，所以nums[m]>target，则right=m

// 版本二  左闭右开即[left, right)
class Solution {public:
    int search(vector& nums, int target) {int left=0;
        int right=nums.size();    //左闭右开，
        while (leftint middle=left+((right-left)>>1);  //防止溢出，(right-left)>>1相当于(right - left)/2
            if(nums[middle]>target){right=middle;//target在左区间，[left,middle)
            }else if(nums[middle]left=middle+1;//target在右区间,[middle+1,right)
            }else{  //nums[middle]==target
                return middle;
            }
        }
        // 未找到目标值
        return -1;
    }
};

下面这句代码中的 (right - left) >>1相当于(right - left)/2

int middle = left + ((right - left) >>1);

原因：还是担心left+right可能会超过基本类型的大值
来源：left + ((right -left) ＞＞ 1

27 移除元素

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

题目链接：27移除元素

题目：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

暴力解法

暴力解法是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
时间复杂度：O(n^2)
空间复杂度：O(1)

//暴力解法  两层for 循环
class Solution {public:
    int removeElement(vector& nums, int val) {int size=nums.size();
        for(int i=0;iif(nums[i]==val){for(int j=i+1;jnums[j-1]=nums[j];   //后面的数往前移
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;
    }
};

双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

• 快指针：寻找新数组需要的元素 ，新数组就是不含有目标元素的数组（删除目标值后的数组）
• 慢指针：指向更新 新数组下标的位置

快指针就是用来创建新数组的，当快指针不等于目标值（要删除的数）时，那就是我们创建的新数组需要的元素，我们要更新数组，把快指针所获取的值赋给新数组所对应的下标的位置，就是把快指针给到慢指针所在的位置，慢指针就是更新新数组的位置。快指针把值赋给慢指针后，慢指针也需要向后移动一个位置来继续更新。当快指针碰到要删除的元素值时，下面的这个for循环里面的内容就不会进行，快指针继续向后移动，慢指针还在原来的位置（这一步就是进行了移除元素）

// 时间复杂度：O(n)
// 空间复杂度：O(1)
//双向指针 快慢指针
class Solution {public:
    int removeElement(vector& nums, int val) {int slowIndex=0;
        for(int fastIndex=0;fastIndexif(val!=nums[fastIndex]){nums[slowIndex++]=nums[fastIndex];
            }
        }
        return slowIndex;  //慢指针对应的下标就是新数组中的大小
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前文章：【Day1】数组、704二分查找、27移除元素-创新互联
链接地址：http://cxhlcq.com/article/ddgisd.html