剑指offer刷题笔记之数组模块
1.二维数组中的查找
两种思路
思路一：二分查找
把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案，时间复杂度是nlogn
public class Solution {
public boolean Find(int target, int [][] array) {
//二分查找
for(int i = 0;i < array.length ;i++){
int low = 0,high = array[i].length-1,mid;
while(low<=high){
mid = (low + high)/2;
if(array[i][mid]>target) high = mid-1;
else if(array[i][mid]<target) low = mid+1;
else return true;
}
}
return false;
}
} 思路二：元素定位比较
当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,即col--；
当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,即row++；
public class Solution {
public boolean Find(int target, int [][] array) {
//刚开始把数定在左下角进行比较
int i = array.length - 1,j = 0;
while((i>=0)&&(j<array[i].length)){
if(target > array[i][j]) j++;
else if(target < array[i][j]) i--;
else return true;
}
return false;
}
} 2.旋转数组的最小数字
思路一：规律关系
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
//原非递减排序的数组：0001 0001112 123 00123 00111
//旋转数组：0100 1120001 312 23001 11100
//第一种思路：遍历求最小数
//第二种思路：找非递减排序的数组旋转的规律
if(array.length == 0) return 0;
for(int i = 0;i < array.length-1;i++){
if(array[i] > array[i+1]) return array[i+1];
if(i == array.length-2) //如果进行到这一步，即前面那步还未得到结果
return array[0];
}
return 0;
}
} 思路二：二分
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
//原非递减排序的数组：000001 0001112 123 00123 001111
//旋转数组：000100 1120001 312 23001 111001
//第三种思路：二分法
if(array.length == 0) return 0;
int low = 0,high = array.length - 1,mid;
while(low <= high){
mid = (low + high)/2;
if(array[mid]>array[high]) low = mid + 1;//如果右半数组为有序数组
else if(array[mid]>array[low]) high = mid;//如果左半数组为有序数组
else high = high - 1;//处理111001这种情况
}
return array[low];
}
} 3.调整数组顺序使奇数位于偶数前面
思路一：冒泡排序
public class Solution {
public void reOrderArray(int [] array) {
//类似冒泡排序
for(int i = 0;i<array.length;i++){
for(int j = array.length - 1;j > 0;j--){
if((array[j]%2==1)&&(array[j-1]%2==0)){
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
}
} 思路二：奇数 与 偶数元素块互换位置
从末尾遍历，若元素为偶数，则在该元素的左边找到最接近的奇数，使得 奇数 与 偶数元素块 互换位置
public class Solution {
public void reOrderArray(int [] array) {
//1 3 2 4 7 5 6 4
if(array.length == 0) return ;
for(int i = 0;i < array.length-1;i++){
if(array[i] %2 == 1) continue;
for(int j = i + 1;j < array.length;j++){//这步的目的是把a[i]这个偶数变为奇数
if(array[j] %2 == 1){//找到奇数，奇数a[j]与偶数块(a[i]--a[j-1])互换
int temp1 = array[j];
for(int h = j;h > i;h--){
array[h] = array[h-1];
}
array[i] = temp1;
break;
}
}
}
}
} 4.数组中出现次数超过一半的数字
思路一：遍历判断
遍历数组，判断array[i]是否为我们所求的数字，复杂度o(n^2)
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0) return 0;
for(int i = 0;i < array.length;i++){//判断array[i]是否为我们所求的数字
int cnt = 0;
for(int j = 0;j < array.length;j++){//找到array[i]在数组中出现的次数
if(array[i]==array[j]) cnt++;
if(cnt*2 > array.length) return array[i];
}
}
return 0;
}
} 思路二：阵地攻守的思想：第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一般即可
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0) return 0;
int cnt = 1,temp = array[0];
// 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
for(int i = 0;i < array.length;i++){
if(cnt == 0){//更新temp的值为当前元素，并置次数为1
temp = array[i];cnt = 1;
}
else if(array[i]==temp) cnt++;
else cnt--;
}
//检查temp是否为答案
cnt = 0;
for(int i = 0;i < array.length;i++){
if(array[i] == temp) cnt++;
}
return (cnt*2>array.length)?temp:0;
}
} --------------continue
