首页 > 代码库 > 剑指offer (8) 旋转数组

剑指offer (8) 旋转数组

2024-07-07 08:39:12   223人阅读

1. 查找和排序

查找：顺序查找、二分查找、二叉搜索树、哈希表
顺序查找：T(n) = O(n)           std::find
二分查找：T(n) = O(log n)      std::binary_search  std::lower_bound  std::upper_bound
哈希表：   T(n) = O(1)           std::unordered_map
 
排序：快速排序、归并排序、堆排序、计数排序、冒泡排序
 
 1 int Partition(std::vector<int>& vec, int first, int last)
 2 {
 3     if (first < 0 || last >= vec.size()) {
 4         throw invalid_argument("invalid_argument");
 5     }
 6 
 7     int index = RandomInRange(first, last);
 8     std::swap(vec.at(index), vec.at(first));
 9     int midIndex = first;
10     for (int i = first + 1; i <= last; ++i) {
11         if (vec.at(i) < vec.at(first)) {
12             swap(vec.at(++midIndex), vec.at(i));
13         }
14     }
15     std::swap(vec.at(first), vec.at(midIndex));
16     return midIndex;
17 }
18 
19 int RandomInRange(int first, int last)
20 {
21     assert(first <= last);
22     int res = rand() % (last - first + 1) + first;
23     return res;
24 }

 

面试题8：旋转数组
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转，例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转
现有一个非降序数组的一个旋转
a. 输出旋转数组的最小元素。
b. 输出旋转数组的最大元素。
c. 查找旋转数组的某个元素。
 
a. 输出旋转数组的最小元素。
旋转之后的数组实际上可以划分为两个排序的子数组，第一个子数组的元素都 >= 第二个子数组的元素
最小和最大 这两个元素刚好组成了 这两个子数组的分界线
 
step1. 我们用两个指针分别指向元素的第一个元素和最后一个元素
step2. 找到数组中间的元素，如果中间元素 >= 第一个指针指向元素，则其位于 第一个子数组，此时 最小元素应该位于 该中间元素的后面，我们可以将第一个指针指向 该中间元素
step3. 如果中间元素 <= 第二个指针指向元素，则其位于 第二个子数组，此时 最小元素应该位于 该中间元素的前面，我们可以将第二个指针指向 该中间元素
 
每次迭代都可以缩小搜索范围，如此往复，第一个指针总是指向 第一个子数组的元素，第二个指针总是指向 第二个子数组的元素，
最终，两个指针会指向两个相邻的元素：
第一个指针指向 第一个子数组的最后一个元素，即该数组的最大值
第二个指针指向 第二个子数组的第一个元素，即该数组的最小值
 
  
 
注意两点：
(1) 数组本身有序的情况，即旋转了0位
(2) 数组中存在重复元素的情况：
  
 
当 vec.at(low) == vec.at(mid) == vec.at(high) 我们无法确认 中间元素是属于第一个子数组 还是第二个子数组，只能采取线性遍历

 

 1 int FindRotateMin(const std::vector<int>& vec)
 2 {
 3     if (vec.size() == 0) {
 4         throw std::invalid_argument("invalid_argument");
 5     }
 6 
 7     int low = 0;
 8     int high = vec.size() - 1;
 9     int mid = low;  // 如果数组原本有序，返回vec.at(mid)正确
10     while (vec.at(low) >= vec.at(high)) {  // 保证 low 总是指向 第一个子数组， high 总是指向 第二个子数组
11         mid = low + (high - low) / 2;
12         if (high - low == 1) return vec.at(high);
13 
14         if (vec.at(low) == vec.at(mid) && vec.at(mid) == vec.at(high)) {
15             return *(std::min_element(vec.begin() + low, vec.begin() + high + 1));
16         }
17 
18         if (vec.at(low) <= vec.at(mid)) {
19                 low = mid;
20             }
21 
22         if (vec.at(mid) <= vec.at(high)) {
23                 high = mid;
24             }
25         }
26     return vec.at(mid);
27 }

 

b. 找出旋转数组的最大值

 1 int FindRotateMax(const std::vector<int>& vec)
 2 {
 3     if (vec.size() == 0) {
 4         throw std::invalid_argument("invalid_argument");
 5     }
 6 
 7     int low = 0;
 8     int high = vec.size() - 1;
 9     int mid = high;
10     while (vec.at(low) >= vec.at(high)) {
11         mid = low + (high - low) / 2;
12         if (high - low == 1) return vec.at(low);
13 
14         if (vec.at(low) == vec.at(mid) && vec.at(mid) == vec.at(high)) {
15             return *(std::max_element(vec.begin() + low, vec.begin() + high + 1));
16         }
17 
18         if (vec.at(low) <= vec.at(mid)) {
19                 low = mid;
20             }
21 
22         if (vec.at(mid) <= vec.at(high)) {
23                 high = mid;
24             }
25         }
26     return vec.at(mid);
27 }

 

c. 查找旋转数组的某个元素

不存在重复元素的情况

存在重复元素的情况


联系
我们