@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree
  • Finger Offer (C++ version) series: finger Offer 09 implements queues with two stacks
  • Offer (C++ version) series: Offer 10-i Fibonacci sequence
  • Sword finger Offer (C++ version) series: sword finger Offer 10-ii frog jump step problem

1, dry

Rotation of the smallest number of elements to the end of an array is called rotation of the array. Take a rotation of an incrementally sorted array and print the smallest element of the rotation array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], whose minimum value is 1. Example 1: input: [3,4,5,1,2] output: 1 example 2: input: [2,2,2,0,1] output: 0 pass count 215,217 submit count 436,094Copy the code

2. Binary search method

Algorithm flow:

  • Initialize: declare left and right Pointers to numbers.
  • Set mid = (left + right) >> 1;
    1. Numbers [mid] > numbers[right] Left = mid (mid + 1, right); left = mid (mid, right); left = mid (mid, right);
    2. If numbers[mid] < numbers[right], mid must be in [left, mid] closed range.
    3. [mid] == mid [left, mid]; [mid + 1, right]; [mid + 1, right] Solution: Execute right = right-1 to narrow the range of judgment.
  • Returns numbers[left] when left == right.
// Interview question 11. Rotate the smallest number in the array
// Standard practice
class Solution {
public:
	int minArray(vector<int>& numbers) {
		int size = numbers.size(a);int left = 0, right = size - 1;
		while (left<right)
		{
			int mid = (left + right) >> 1;
			if (numbers[mid]>numbers[right])
			{
				left = mid + 1;
			}
			else if (numbers[mid]<numbers[right])
			{
				right = mid;
			}
			else{ right--; }}returnnumbers[left]; }};Copy the code

4. Complexity

/* time complexity O(log2N) : in special cases (e.g. [1,1,1,1]), it degrades to O(N). Space complexity O(1) : Left, right, mid Pointers use extra space of constant size. * /
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array
  • Sword finger Offer (C++ version) series: sword finger Offer 04 2d array lookup
  • Offer (C++ version) series: Offer 05 replace blank
  • Finger Offer (C++ version) series: finger Offer 06 prints linked lists from end to end
  • Sword finger Offer (C++ version) series: sword finger Offer 07 rebuild binary tree
  • Finger Offer (C++ version) series: finger Offer 09 implements queues with two stacks
  • Offer (C++ version) series: Offer 10-i Fibonacci sequence
  • Sword finger Offer (C++ version) series: sword finger Offer 10-ii frog jump step problem

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…