赞
踩
本题要求在升序数组中查找目标元素的下标,采用暴力算法扫描数组的时间复杂度为O(n),而使用二分查找法的时间复杂度为O(log2n)。使用二分查找法需要把握目标元素所在数组的起始下标、中点下标和终止下标的关系,通过二分查找可以将目标数组不断缩小直到找到目标元素。
具体代码如下:
- class Solution {
- public:
- int search(vector<int>& nums, int target) {
- int n=nums.size();
- int low=0;
- int high=n-1;
- while(low<=high)
- {
- int mid=(low+high)/2;
- if(target>nums[mid])
- {
- low=mid+1;
- }
- else if(target<nums[mid])
- {
- high=mid-1;
- }
- else if(target==nums[mid])
- {
- return mid;
- }
- }
- return -1;
- }
- };
本题要求在目标数组中删除值等于val的元素,下面展示两种解法。
法一:从数组开头扫描,遇到值等于val的元素就将其与当前数组最后一个元素互换而后将数组的长度减一,直到扫描的元素为当前数组的最后一个元素。
具体代码如下:
- class Solution {
- public:
- int removeElement(vector<int>& nums, int val) {
- int n=nums.size();
- int i=0;
- while(i<n)
- {
- if(nums[i]==val)
- {
- int temp=nums[i];
- nums[i]=nums[n-1];
- nums[n-1]=temp;
- n--;
- }
- else
- {
- i++;
- }
- }
- return n;
- }
- };
法二:使用左右指针,左右指针开始均指向第一个元素,如果右指针指向的元素值不为val,将右指针指向的元素值代替左指针指向的元素值,左右指针均向右移动1;如果右指针指向的元素值为val,则将右指针向右移动1,左指针不动,直到右指针遍历完整个数组为止。这样左指针之前的元素值均不为val。
具体代码如下:
- class Solution {
- public:
- int removeElement(vector<int>& nums, int val) {
- int n = nums.size();
- int left = 0;
- for (int right = 0; right < n; right++) {
- if (nums[right] != val) {
- nums[left] = nums[right];
- left++;
- }
- }
- return left;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。