演算法訓練營
- 1. 核心考點：陣列相關，特性觀察，時間復雜度把握
- 2. 核心考點：陣列理解，二分查找，臨界條件
- 3.核心考點：陣列操作，排序思想的擴展使用
1. 核心考點：陣列相關，特性觀察，時間復雜度把握
注意：
1.查找的程序本質是排除的程序，
2.一次排除一行或一列，
3.從左上角或者右下角開始，可以一次排除一行或者一列
int i = 0;
int j = array[0].size()-1;
while( i < array.size() && j >= 0){
if(target < array[i][j]){ //array[i][j]一定是當前行最大的，當前列最小的
//target < array[i][j] 排除當前列
j--;
}
else if(target > array[i][j]){
//target > array[i][j] 排除當前行
i++;
}
else{
//找到
return true;
}
}
return false;
}
};
2. 核心考點：陣列理解，二分查找，臨界條件
這道題第一種方法就是遍歷一遍找最小的數，這里我們把代碼附上就不詳細講了，
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.empty())
{
return 0;
}
int i = 0;
int lit = rotateArray[0];
for (i = 0; i < rotateArray.size(); i++)
{
if (rotateArray[i] < lit)
{
lit = rotateArray[i];
}
}
return lit;
}
};
第二種方法：采用二分查找的方式，進行定位，
定義首尾下標，因為是非遞減陣列旋轉，所以旋轉最后可以看做成兩部分，前半部分整體非遞減，后半部分整體非遞減，前半部分整體大于后半部分，
所以，我們假設如下定義，left指向最左側，right指向最右側，mid為二分之后的中間位置，逐步縮減范圍，/當left和right相鄰時，right指向的位置，就是最小元素的位置，
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int left = 0;
int right = rotateArray.size() - 1;
int mid = (left + right) >> 1;
while (rotateArray[left] >= rotateArray[right])
{
if (right - left == 1)
{
mid = right;
break;
}
mid = left + ((right - left) >> 1);
if (rotateArray[mid] == rotateArray[left] && rotateArray[left] == rotateArray[right])
{
int result = rotateArray[left];
for (int i = left + 1; i < right; i++)
{
if (result>rotateArray[i]){
result = rotateArray[i];
}
}
return result;
}
if (rotateArray[left] <= rotateArray[mid])
{
left = mid;
}
else
{
right = mid;
}
}
return rotateArray[mid];
}
};
3.核心考點：陣列操作，排序思想的擴展使用
我們先求出來奇數，然后將這個奇數保存起來，將該奇數之前的內容(偶數序列)，整體后移一個位置將奇數保存在它將來改在的位置，因為我們是從左往右放的，沒有跨越奇數，所以一定是相對位置不變的，
int i = 0;
int k = 0;
for (i = 0; i < array.size() - 1; i++)
{
if (array[i] & i == 1)
{
int tmp = array[i];
int j = i;
while (j>0)
{
array[j] = array[j - 1];
j--;
}
array[k++] = tmp;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297285.html
標籤：其他