【算法训练营】（day1）

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;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二种方法：采用二分查找的方式，进行定位。
定义首尾下标，因为是非递减数组旋转，所以旋转最后可以看做成两部分，前半部分整体非递减，后半部分整体非递减，前半部分整体大于后半部分。
所以，我们假设如下定义，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];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16