Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
思路
标记原有数组，j标记新数组
i，j分别是快，慢指针
c++1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int removeDuplicates(vector<int>& nums) { //引用
if(nums.empty()) return 0; //特殊情况
int j = 0;
for(int i = 1;i < nums.size();i++){
if(nums[j] != nums[i])
nums[++j] = nums[i];
}
return j + 1;
}
};
c++1
2
3
4
5
6class Solution {
public:
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(),unique(nums.begin(),nums.end()));
} //distance(),unique()两个函数都是STL函数
};
python31
2
3
4
5
6
7
8
9
10class Solution:
def removeDuplicates(self, nums: List[int]) -> int: # ->明确函数返回值类型和参数
if len(nums)==0:
return 0
j = 0
for i in range(1,len(nums)): # range用法，一个参数默认从0开始
if nums[i] != nums[j]:
j += 1
nums[j] = nums[i]
return j + 1 # 数组最大下标 + 1 = 数组大小
Remove Duplicates from Sorted Array II
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
思路
使用快，慢指针，快指针标记原有序列，慢指针标记新序列
临界条件是新序列不能同时存在连续三个相同的数，而根据题意，序列有序，所以只要保证排除连续三个数中第一个和第三个相同这种情况即可
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int j = 0;
int tag = 1;
for(int i=1;i<nums.size();i++){
if(nums[j] != nums[i]){
nums[++j] = nums[i];
tag = 1;
}
else if (tag >= 2){
continue;
}
else{
nums[++j] = nums[i];
tag++;
}
}
return j+1;
}
};
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 2) return nums.size();
int j=2;
for(int i=2;i<nums.size();i++){
if(nums[i] == nums[j-2]){
continue;
}
else{
nums[j++] = nums[i];
}
}
return j;
}
};
python1
2
3
4
5
6
7
8
9
10class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums)<=2:
return len(nums)
index = 2
for i in range(2,len(nums)):
if(nums[index-2] != nums[i]):
nums[index] = nums[i]
index += 1
return index
Search in rotated sorted array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
思路
采用二分搜索的办法，设置好二分搜索的边界
当搜索区域的中值确定之后，两个子区域总有一个区域是有序的
而另一个无序子区域就是与之前的所搜区域相似
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
int search(vector<int>& nums, int target) {
int first = 0;
int last = nums.size();
while(first != last){
const int mid = (first + last ) /2 ;
if(nums[mid] == target){
return mid;
}
if(nums[first] < nums[mid]){
if(nums[first] <= target && target <nums[mid])
last = mid;
else
first = mid + 1;
}
else{
if (nums[mid] < target && target <= nums[last-1])
first = mid + 1;
else
last = mid;
}
}
return -1;
}
};
python
1 | class Solution: |
Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
思路
与上一题目比出现了一种特殊情况，1 3 1 1 1这种类似的情况
也就是nums[middle] == nums[first]时，[first,middle]并不有序的情况
当不存在重复数据时，这种情况不可能出现
当有重复数据时，这种情况才可能出现，单独拿出来处理一下
处理办法：让first++即可
1 | class Solution { |
python1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution:
def search(self, nums: List[int], target: int) -> bool:
first = 0
last = len(nums)
if last == 0:
return False
while first < last:# 一定要注意二分查找的条件，提交过程中因为把while的条件写成了 while first <= last: 在这卡了很长时间，一直提示list index out of range 为什么会出现这种问题呢? 因为当list为0个或者1个元素的时候，二分循环条件里包含等号，循环会多一次，index of middle 会大于list长度
middle = first + (last - first) // 2
if nums[middle] == target:
return True
if nums[first] < nums[middle]:
if nums[first] <= target and nums[middle] > target:
last = middle
else:
first = middle + 1
elif nums[first] > nums[middle]:
if nums[middle] < target and nums[last - 1] >= target:
first = middle + 1
else:
last = middle
else:
first += 1
return False
补充—关于二分搜索的标准代码
用python语言描述：
C++标准库1
2
3
4
5
6
7
8def lower_bound(array,first,last,value):#返回[first,last)内第一个不小于value的值的位置
while first < last:#搜索区间[first，last)不为空
mid = first + (last - first) //2 #防溢出
if array[mid] < value:
first = mid + 1
else:
last = mid
return first
Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public:
double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
int m = A.size();
int n = B.size();
int total = m + n;
if(total & 0x1) //total是奇数，偶数
return find_kth(A.begin(),m,B.begin(),n,total/2 + 1);
else
return (find_kth(A.begin(),m,B.begin(),n,total / 2) //上位中位数
+ find_kth(A.begin(),m,B.begin(),n,total/2 + 1)) /2.0;//下位中位数
}
private:
static int find_kth(std::vector<int>::const_iterator A,int m, //找到两个有序数组中第k大的数
std::vector<int>::const_iterator B,int n,int k){
if(m>n)return find_kth(B,n,A,m,k);
if(m==0)return *(B+k-1);
if(k==1)return min(*A,*B);
//DIVIDE K INTO TWO PARTS
int ia = min(k/2,m),ib = k - ia;
if(*(A + ia -1) < *(B + ib - 1))
return find_kth(A + ia,m - ia,B,n,k - ia);
else if (*(A + ia -1) > *(B + ib - 1))
return find_kth(A,m,B + ib,n - ib,k - ib);
else
return A[ia - 1];
}
};
END~