@[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;
- Numbers [mid] > numbers[right] Left = mid (mid + 1, right); left = mid (mid, right); left = mid (mid, right);
- If numbers[mid] < numbers[right], mid must be in [left, mid] closed range.
- [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…