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;
    }
}

思路二：元素定位比较

另一种：利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较，
当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