请教一道经典题

请教大家一道经典题。
sorted array after rotation. return the starting index for the minimum element.
[1,1,1,1,1,1] -> 0
[1,1,1,2,1,1] -> 4
谢谢各位大佬。

Andrew007 发表于 2021-3-24 03:43
非常感谢大神的解答和耐心。🐂

谢谢你给了这么多test case，开始是真没想到。只是第一感觉应该用BS，具体还是有很多要注意的点啊。

Andrew007 发表于 2021-3-24 02:51
这个能过不？[2,1,1,1,2]目前我想的case有
    cout

大意了，没考虑这么多case

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. using namespace std;
   
6. int findMin(vector<int> nums) {
   
7.     if(nums.front() < nums.back()) return 0;
   
8.     int left = 0, right = nums.size() - 1;
   
9.     int front = nums[0];
   
10.    
    
11.     while(left < right-1 && nums[left] >= nums[right])
    
12.     {
    
13.         if(nums[left]==nums[left+1])
    
14.             left++;
    
15.         else if(nums[right]==nums[right-1])
    
16.             right--;
    
17.         else
    
18.         {
    
19.             int mid = left + (right - left) / 2;
    
20.             if(nums[mid] > nums[right]) left = mid;
    
21.             else if(nums[mid] < nums[left]) right = mid;
    
22.             else left++,right--;
    
23.         }
    
24.     }
    
25.     if(left==right-1&&nums[left]==front&&nums[right]==front)return 0;
    
26.     return nums[left]<nums[right]?right+1:right;
    
27. }
    
28. int main()
    
29. {
    
30.     cout << findMin({1,2,3,6,1}) << endl;
    
31.     cout << findMin({1,1,1,2,1,1}) << endl;
    
32.     cout << findMin({1,2,1,1,1}) << endl;
    
33.     cout << findMin({1,1,1,1,1}) << endl;
    
34.     cout << findMin({2,2,1,1,2,2}) << endl;
    
35.     cout << findMin({2,2,3,3,2,2}) << endl;
    
36.     return 0;
    
37. }
    
38. 
    
39. 
    
40. 
    
41. 
    

复制代码

这会的输出是，应该是对的
4                                                                                                                                      
4                                                                                                                                      
2                                                                                                                                      
0                                                                                                                                      
2                                                                                                                                      
4                                                                                                                                      
                                                                                                                                       
                                                                                                                                       
...Program finished with exit code 0                                                                                                   
Press ENTER to exit console.   

Andrew007 发表于 2021-3-24 02:14
非常感谢。还有一些小bug，但是已经很好了。 比如 [1,2,1,1,1], [1,1,1,1,1]. 继续加米。

刚测了一下【1，2，1，1，1】这个的输出是2，这个应该是正确的吧
【1，1，1，1，1】确实没考虑
改了一下，这种情况下，最坏情况会变成O(n)时间，平均是O(lg(n))

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <vector>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. int findMin(vector<int> nums) {
   
8.     if(nums.front() < nums.back()) return 0;
   
9.     int left = 0;
   
10.     int right = nums.size()-1;
    
11.     while(left<right&&nums[left]==nums[right]){left++;right--;}
    
12.     if(left == right) return 0;
    
13.     while(left < right-1 && nums[left] >= nums[right])
    
14.     {
    
15.         int mid = left + (right - left) / 2;
    
16.         if(nums[mid] > nums[right]) left = mid;
    
17.         else if(nums[mid] < nums[left]) right = mid;
    
18.         else left++,right--;
    
19.     }
    
20.     return nums[left]<nums[right]?right+1:right;
    
21. 
    
22. }
    
23. int main()
    
24. {
    
25.     cout << findMin({1,2,3,6,1}) << endl;
    
26.     cout << findMin({1,1,1,2,1,1}) << endl;
    
27.     cout << findMin({1,2,1,1,1}) << endl;
    
28.     cout << findMin({1,1,1,1,1}) << endl;
    
29.     return 0;
    
30. }
    

复制代码

目前这个的输出是 4 4 2 0， 应该是正确的吧？

二分法求最后一个最大值，然后输出他的后一位？

tigerwash 发表于 2021-3-23 04:40
二分法求最后一个最大值，然后输出他的后一位？

这可以用来求 [2,1,1,1,2]吗？

经典题难道不应该看经典解答吗
你是看不懂还是懒得查？

补充内容 (2021-3-23 05:48):
我记得是一开始把21112前后的2去掉一个之后二分。

可以重复的我记得没法二分，只能暴力On

LC 154咯

用BS吧？

1.   
   
2. int findMin(vector<int>& nums) {
   
3.         int left = 0;
   
4.         int right = nums.size()-1;
   
5.         while(left < right-1 && nums[left] >= nums[right])
   
6.         {
   
7.             int mid = left + (right - left) / 2;
   
8.             if(nums[mid] > nums[right]) left = mid;
   
9.             else if(nums[mid] < nums[left]) right = mid;
   
10.             else left++,right--;
    
11.         }
    
12.         return nums[left]<nums[right]?left:right;
    
13.     }
    

复制代码

twtypsj 发表于 2021-3-23 10:37
用BS吧？
[mw_shl_code=cpp,true]  
int findMin(vector& nums) {

运行了一下，结果好像不对。[1,1,1,2,1,1] 返回了2.

junlico 发表于 2021-3-23 08:22
LC 154咯

不是原题。 这个是找index。

一剑终情 发表于 2021-3-23 07:21
可以重复的我记得没法二分，只能暴力On

可能。当时面试的时候，面试官让我在二分的基础上改。当时没写出来，不是找最左就是最右。