leecode[三]
153. 寻找旋转排序数组中的最小值
思路一：
比较暴力的求解，找到翻转的点（由升序变为降序），有找到这个点，则就是下一个点就是。没有找到这个点，就是第一个点。
class Solution {
public:
int findMin(vector<int>& nums) {
int size = nums.size();
int i,tmp;
if(size==1){
return nums[0];
}
for(i=1,tmp=nums[0];i<size;i++){
if(nums[i]<tmp){
break;
}
tmp=nums[i];
}
if(i!=size){
return nums[i];
}else{
return nums[0];
}
}
};
思路二：
我们需要知道，对于一个区间A，如果A[start] < A[stop]，那么该区间一定是有 序的了。
另外，由于不含重复元素，需要分两种情况。
对于一个轮转了的排序了的数组，
如果nums[mid]>nums[left]，最小值一定在右半区间
如果nums[mid]<nums[left]，最小值一定在左半区间
class Solution {
public:
int findMin(vector<int>& nums) {
for (int low = 0, high = nums.size() - 1; low <= high;){
if (nums[low] <= nums[high]){
return nums[low];
}
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]){
low = mid + 1;
} else {//[3,1,2]
high = mid;
}
}
return INT_MIN;
}
};
static const auto __lamda = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
238. 除自身以外数组的乘积
正序成一次，逆序乘一次，每次的时间复杂度都是O（n）
即：
0 1 1x2 1x2x3
4x3x2, 4x3, 4, 0
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> shun;
int size=nums.size();
int tmp=1;
shun.push_back(1);
for(int i=1;i<size;i++){
shun.push_back(shun[i-1]*nums[i-1]);
}
for(int j=1;j<size;j++){
tmp=tmp*nums[size-j];
shun[size-j-1]*=tmp;
}
return shun;
}
};