做网站 服务器多少钱一年,课程网站建设的财务分析,湖北建设厅网站,大气网站首页目录 1. 朴素二分查找2. 在排序数组中查找元素的第一个和最后一个位置3. 搜索插入位置4. x的平方根5. 山脉数组的峰值索引6. 寻找峰值7. 寻找旋转排序数组中的最小值8. 点名 1. 朴素二分查找 题目信息#xff1a; 题目链接#xff1a; 二分查找二分查找的使用前提为数据具有 题目链接 二分查找二分查找的使用前提为数据具有二段性在二分时并不一定要进行2等分1/31/4…二分查找的时间复杂度O( l o g N log^N logN) 求mid的算法优化原算法有溢出风险 class Solution
{
public:int search(vectorint nums, int target) {int right nums.size() - 1;int left 0;while(right left){//此种算法存在溢出风险//int mid (right left) / 2;int mid (right - left) / 2 left;if(nums[mid] target){right mid - 1;}if(nums[mid] target){left mid 1;}if(nums[mid] target){return mid;}}return -1;}
};2. 在排序数组中查找元素的第一个和最后一个位置 题目信息 题目链接 在排序数组查找元素的第一个与最后一个位置思路向符合条件位置不断推进 class Solution {
public:vectorint searchRange(vectorint nums, int target) {int right nums.size() - 1;int left 0;vectorint count(2,-1);//数据为空特殊处理if(nums.size() 0){return count;}//左端点while(left right){//落到左区间int mid left (right - left) / 2;if(nums[mid] target){right mid;}if(nums[mid] target){left mid 1;}}if(nums[left] target){count[0] left;}right nums.size() - 1;left 0;//右端点while(left right){//落到右区间int mid left (right - left 1) / 2;if(nums[mid] target){right mid - 1;}if(nums[mid] target){left mid;}}if(nums[left] target){count[1] left;}return count;}
};3. 搜索插入位置 题目信息 题目链接 搜索插入位置思路取大右区间的左边界 class Solution
{
public:int searchInsert(vectorint nums, int target) {int left 0;int right nums.size();while(left right){//小于大于等于int mid left (right - left) / 2;if(nums[mid] target){left mid 1;}if(nums[mid] target){right mid;}}return left;}
};4. x的平方根 题目信息 题目链接 x的平方根思路暴力解法的优化左区间的右边界二段性 class Solution
{
public:int mySqrt(int x) {if(x 1){return 0;}int left 1;int right x;while(left right){//当left从0开始时left 1可能会溢出long long mid left (right - left 1) / 2;//防止溢出if(mid * mid x){left mid;}if(mid * mid x){right mid - 1;}}return left;}
};5. 山脉数组的峰值索引 题目信息 题目链接 山脉数组的峰值索引思路二分法左区间右边界 class Solution
{
public:int peakIndexInMountainArray(vectorint nums) {//左区间右边界int left 0;int right nums.size() - 1;while(left right){int mid left (right - left 1) / 2;if(nums[mid] nums[mid - 1]){left mid;}if(nums[mid] nums[mid - 1]){right mid - 1;}}return left;}
};右区间的左边界 class Solution
{
public:int peakIndexInMountainArray(vectorint nums) {//右区间左边界int left 0;int right nums.size() - 1;while(left right){int mid left (right - left) / 2;if(nums[mid] nums[mid 1]){left mid 1;}if(nums[mid] nums[mid 1]){right mid;}}return left;}
};6. 寻找峰值 题目信息 题目链接 寻找峰值思路二段性右区间的左边界不足三个数特殊化处理 class Solution
{
public:int findPeakElement(vectorint nums) {int left 0;int right nums.size() - 1;//特殊情况//数组值小于3if (nums.size() 2){return 0;}if (nums.size() 3){return nums[0] nums[1] ? 0 : 1;}//右区间的左边界while (left right){int mid left (right - left) / 2;if (nums[mid] nums[mid 1]){left mid 1;}if (nums[mid] nums[mid 1]){right mid;}}return left;}
};7. 寻找旋转排序数组中的最小值 题目信息 题目链接 寻找寻转排序数组中的最小值思路右区间左边界 class Solution
{
public:int findMin(vectorint nums) {//二段性右区间左边界int right nums.size() - 1;int left 0;while(left right){int mid left (right - left) / 2;if(nums[mid] nums[right]){left mid 1;}if(nums[mid] nums[right]){right mid;}}return nums[left];}
};8. 点名 题目信息 题目链接 点名思路多解法考察知识广度 1二分法右区间的左边界学号等于下标学号大于下标边界问题 2 哈希表法时间复杂度O(n)空间复杂度O(n) 3 异或法 4 等差数列求和 5 暴力遍历法 class Solution {
public:int takeAttendance(vectorint records) {int left 0;int right records.size() - 1;while(left right){int mid left (right - left) / 2;if(records[mid] mid){left mid 1;}if(records[mid] mid){right mid;}}//边界问题n-1个元素n个学生必定有一人缺席缺席为学号最后一位的学生if(left records.size() - 1 left records[left]){left;}return left;}
};等差数列 class Solution
{
public:int takeAttendance(vectorint records) {//等差数列求和首项加末项乘以项数除以2int sum ((0 records.size()) * (records.size() 1)) / 2;for(int i 0; i records.size(); i){sum - records[i];}return sum;}
};哈希表 class Solution
{
public:int takeAttendance(vectorint records) {//哈希表法int n records.size() 1;int* hash (int*)malloc(n * sizeof(int));//单位字节memset(hash, 0, n * sizeof(int));int i 0;for(i 0; i records.size(); i){hash[records[i]];}for(i 0; i n; i){if(hash[i] 0){break;}}return i;}
};暴力遍历 class Solution
{
public:int takeAttendance(vectorint records) {//暴力遍历int cur 0;while(cur records.size()){if(cur ! records[cur]){break;}cur;}if(cur records.size() - 1 records[cur] cur){cur;}return cur;}
};异或法 class Solution
{
public:int takeAttendance(vectorint records){//异或法int sum 0;for(int i 0; i records.size() 1; i){sum ^ i;}for(int i 0; i records.size(); i){sum ^ records[i];}return sum;}
};
