公式：f(0) = 0, f(1) = 1, f(2)=1, f(n)=f(n-1)+f(n-2)
递归
int fibona(int n)
{
if(n==0)
retrurn 0;
if(n==1 || n==2)
return 1;
return fibona(n-1)+fibona(n-2);
}非递归
int fibona(int n)
{
if(n==0)
retrurn 0;
if(n==1 || n==2)
return 1;
int a = 1;
int b = 1;
int num = 0;
for(int i=3;i<=n;i++)
{
num = a+b;
a = b;
b=num;
}
return num;
}给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
由于所有的数字都是1-n之间，而且只存在一个重复数字，如果没有重复数，那么刚好就是n个数字，mid = (0+n-1)/2，遍历一遍数组，计算小于等于mid的值的个数，
如果没有重复数，小于等于mid的数字刚好是mid个(1,2,...mid)，如果个数大于mid，说明在（1，mid）之间，存在重复的数字；反之，如果个数小于等于mid，说明（mid+1,n）之间，
存在重复的数字；
示例 1:
arr = [1,3,4,2,2]
mid = (0 + 4) / 2 = 2 arr小于等于的2有3个（1，2，2），所以小于mid（2）的1-2中，肯定有重复的值，
high = mid=2，low = 0
mid = (0 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
low=mid+1=2，hight=2，不满足while条件，所以这个重复值就是2
所以重复的数是 2
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low = 0;
int high = nums.size() -1;
while(low < high)
{
int mid = (low+high) / 2;
int count = 0;
for(size_t i=0;i<nums.size();i++)
{
if(nums[i] <= mid)
{
count += 1;
}
}
if(count <= mid)
low = mid+1;
else
high = mid;
}
return low;
}
};1、整个数组分为两部分，第一部分是一个大顶堆，第二部分是一个小顶堆；
2、在插入的过程中，保证第一部分和第二部分的数量相差不超过1，且大顶堆的最大值不超过小顶堆的最小值；
3、优先插入大顶堆，当数量大于小顶堆的时候，把大顶堆的最大值向小顶堆转移；注意，大顶堆只有一个数组的时候，不要转移；
4、当两个堆数量相等的时候，如果大顶堆的最大值大于小顶堆的最小值，那么交换，并重新调整堆；
class MedianFinder {
public:
/** initialize your data structure here. */
std::vector<int> minHeap;
std::vector<int> maxHeap;
MedianFinder() {
minHeap.clear();
maxHeap.clear();
}
void adjustMaxHeap(std::vector<int>& maxHeap,int currentIndex)
{
int parentIndex = findParentNodeIndex(currentIndex);
if(parentIndex < 0 || parentIndex >= maxHeap.size())
{
return;
}
if(maxHeap[parentIndex] < maxHeap[currentIndex])
{
int temp = maxHeap[parentIndex];
maxHeap[parentIndex] = maxHeap[currentIndex];
maxHeap[currentIndex] = temp;
adjustMaxHeap(maxHeap,parentIndex);
}
}
void adjustMaxHeapFromTop(std::vector<int>& heap, int currentIndex)
{
if (currentIndex >= heap.size() || currentIndex < 0)
{
return;
}
// 取左孩子
int iLeftIndex = findLeftNodeIndex(currentIndex);
if (iLeftIndex >= heap.size() || iLeftIndex < 0)
{
return;
}
if (heap[currentIndex] < heap[iLeftIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iLeftIndex];
heap[iLeftIndex] = temp;
adjustMaxHeapFromTop(heap, iLeftIndex);
}
// 取右节点
int iRightIndex = findRightNodeIndex(currentIndex);
if (iRightIndex >= heap.size() || iRightIndex < 0)
{
return;
}
if (heap[currentIndex] < heap[iRightIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iRightIndex];
heap[iRightIndex] = temp;
adjustMaxHeapFromTop(heap, iRightIndex);
}
}
void adjustMinHeapFromTop(std::vector<int>& heap,int currentIndex)
{
if(currentIndex >= heap.size() || currentIndex < 0)
{
return;
}
// 取左孩子
int iLeftIndex = findLeftNodeIndex(currentIndex);
if(iLeftIndex >= heap.size() || iLeftIndex < 0)
{
return;
}
if(heap[currentIndex] > heap[iLeftIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iLeftIndex];
heap[iLeftIndex] = temp;
adjustMinHeapFromTop(heap,iLeftIndex);
}
// 取右节点
int iRightIndex = findRightNodeIndex(currentIndex);
if(iRightIndex >= heap.size() || iRightIndex < 0)
{
return;
}
if(heap[currentIndex] > heap[iRightIndex])
{
int temp = heap[currentIndex];
heap[currentIndex] = heap[iRightIndex];
heap[iRightIndex] = temp;
adjustMinHeapFromTop(heap,iRightIndex);
}
}
int findParentNodeIndex(int index)
{
return floor((index -1 )/2);
}
int findLeftNodeIndex(int index)
{
return 2*index+1;
}
int findRightNodeIndex(int index)
{
return 2*index+2;
}
void adjustMinHeap(std::vector<int>& minHeap,int currentIndex)
{
// 1、找到父节点
int parentIndex = findParentNodeIndex(currentIndex);
if(parentIndex < 0)
{
return;
}
if(minHeap[parentIndex] > minHeap[currentIndex])
{
int temp = minHeap[parentIndex];
minHeap[parentIndex] = minHeap[currentIndex];
minHeap[currentIndex] = temp;
adjustMinHeap(minHeap,parentIndex);
}
}
void addNum2MaxHeap(int num)
{
maxHeap.push_back(num);
adjustMaxHeap(maxHeap,maxHeap.size()-1);
if ((maxHeap.size() > minHeap.size()) && maxHeap.size() > 1)
{
int max = maxHeap[0];
addNum2MinHeap(max);
maxHeap[0] = maxHeap[maxHeap.size()-1];
maxHeap.pop_back();
adjustMaxHeapFromTop(maxHeap,0);
}
if ((maxHeap.size() == minHeap.size()) && maxHeap.size() >= 1)
{
if (maxHeap[0] > minHeap[0])
{
int tmp1 = maxHeap[0];
int tmp2 = minHeap[0];
maxHeap[0] = tmp2;
adjustMaxHeapFromTop(maxHeap, 0);
minHeap[0] = tmp1;
adjustMinHeapFromTop(minHeap, 0);
}
}
}
void addNum2MinHeap(int num)
{
minHeap.push_back(num);
adjustMinHeap(minHeap,minHeap.size()-1);
}
void addNum(int num) {
addNum2MaxHeap(num);
}
double findMedian() {
if((minHeap.size() + maxHeap.size()) % 2 == 0)
{
double t = (double)minHeap[0] + (double)maxHeap[0];
return t /2;
}
if(minHeap.size() > maxHeap.size() )
{
return minHeap[0];
}
return maxHeap[0];
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/