哈希表的主要优点是在
时间内查找某一元素，是效率最高的查找方式；但是缺点是需要额外的空间来实现哈希表。
旋转数组的最小数字：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.empty())
return 0;
//头部和尾部位置，指向两个排序好的子数组
int indexFirst = 0;
int indexLast = rotateArray.size()-1;
//若全部数都旋转一次，最小值为首元素
int indexMiddle = indexFirst;
while(rotateArray[indexFirst]>=rotateArray[indexLast])
{
//若相邻，那么右边索引在最小值处
if(indexFirst+1 == indexLast)
return rotateArray[indexLast];
indexMiddle = (indexLast+indexFirst)/2;
//indexMiddle = (indexLast-indexFirst)/2 + indexFirst;
if((rotateArray[indexFirst] == rotateArray[indexLast]) && (rotateArray[indexLast]==rotateArray[indexMiddle]))
return search(rotateArray,indexFirst,indexLast);
if(rotateArray[indexMiddle]>=rotateArray[indexFirst])
{
indexFirst = indexMiddle;
}
//若不是右子数组最小的位置
else if(rotateArray[indexMiddle]<=rotateArray[indexLast])
indexLast = indexMiddle;
}
}
private:
int search(const vector<int> &arr,const int left, const int right)
{
int min=arr[left];
for(int i=left+1; i<=right; ++i)
if(arr[i]>min) min=arr[i];
return min;
}
};
53、
统计一个数字在排序数组中出现的次数。
- 因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5 这两个数应该插入的位置，然后相减即可。只是取的距离k最近的值，由于都是整数，原数组中可能存在k-1或者k+1；而k+0.5和k-0.5之间保证只有数字k。
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
}
private:
int biSearch(const vector<int> &data, double k)
{
int start=0, end=data.size()-1;
int mid;
while(start<=end)
{
mid = start + (end-start)/2;
if(data[mid]>k)
end = mid-1;
else if (data[mid]<k)
start = mid+1;
}
//start是这个端点
return start;
}
};
57、和为s的一对数
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
- 解析： //假设：若b>a,且存在，
//a + b = s;
//(a - m ) + (b + m) = s
//则：(a- m)(b + m)=ab - (b-a)m - m*m < ab；说明外层的乘积更小
class Solution {
public:
//假设：若b>a,且存在，
//a + b = s;
//(a - m ) + (b + m) = s
//则：(a- m)(b + m)=ab - (b-a)m - m*m < ab；说明外层的乘积更小
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
if(array.empty()) return vector<int>();
vector<int> ans;
vector<int>::iterator first=array.begin();
vector<int>::iterator last=array.end()-1;
while(first<last)
{
int fnum = *first, lnum= *last;
if(fnum+lnum == sum)
{
ans.push_back(fnum);
ans.push_back(lnum);
break;
}
else if(fnum + lnum < sum)
first++;
else
last--;
}
return ans;
}
};
2.和为连续整数的序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
- 解析：考虑用small和big分别表示序列的最小值和最大值，初始化，small=1与big=2，如果序列和大于sum，那么去掉最小的small也就是说更新small++；小于序列的话，增大big，同时把small到big的和curSum更新；
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
if(sum<3) return vector<vector<int>>();
vector<vector<int>> ans;
int small=1, big=2, mid=sum/2;
int curSum=small+big;
//等于3的时候
if(curSum==sum)
ans.push_back(initVec(small,big));
while(small<mid)
{
//当前的和等于总和
if(curSum==sum)
{
ans.push_back(initVec(small,big));
}
//当前的和大于总和；最小的左边未超出中位数
while(curSum>sum && small <mid)
{
curSum-=small;
small++;
if(curSum==sum)
ans.push_back(initVec(small,big));
}
//当前的和小于总和,再加入大一位的数，并填入总和内
big++;
curSum+=big;
}
return ans;
}
private:
vector<int> initVec(int first, int last)
{
vector<int> vec;
for(int i=first;i<=last;++i)
vec.push_back(i);
return vec;
}
};
