剑指offer 数组专题 刷题记录（1）

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0||array==null){
            return false;
        }
        for(int i=0;i<array.length;i++){
            int begin=0;
            int end=array[i].length-1;
            while(begin<=end){
               int mid=(begin+end)/2;
                if(target==array[i][mid]){
                    return true;
                }else if(target<array[i][mid]){
                    end=mid-1;
                }else if(target>array[i][mid]){
                    begin=mid+1;
                }
            }
        }
        return false;
    }
}

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row=0;
        int col=array[0].length-1;
        while(row<array.length&&col>=0){
            if(array[row][col]==target){
                return true;
            }else if(target>array[row][col]){
                row++;
            }else if(target<array[row][col]){
                col--;
            }
        }
        return false;
    }
}

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        //二分查找
        if(array.length==0||array==null){
            return 0;
        }
        int start=0;
        int end=array.length-1;
        int mid=0;
        while(array[start]>=array[end]){
            if(end-start==1){
                return array[end];
            }
            mid=start+(end-start)/2;
            if(array[mid]>=array[start]){
                start=mid;
            }else{
                end=mid;
            }
        }
        return array[mid];
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        ArrayList<Integer> oddList = new ArrayList<>();
        ArrayList<Integer> evenList = new ArrayList<>();
        int[] res = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if (0 == array[i] % 2) {
                // 偶数
                evenList.add(array[i]);
            } else {
                // 奇数
                oddList.add(array[i]);
            }
        }
        for (int i = 0; i < oddList.size(); i++) {
            res[i] = oddList.get(i);
        }
        int index = oddList.size();
        for (int i = 0; i < evenList.size(); i++) {
            res[index] = evenList.get(i);
            index++;
        }
        return res;
    }
}

//解题思路
/*（O(n),O(n)）
遍历两次数组，第一次只添加奇数到新数组里，第二次只添加奇数到新数组里
 */
public int[] reOrderArray (int[] array) {
    int index = 0;
    int[] res = new int[array.length];
    for (int i : array) {
        if (i % 2 != 0) {
            res[index] = i;
            index++;
        }
    }
    for (int i : array) {
        if (i % 2 == 0) {
            res[index] = i;
            index++;
        }
    }
    return res;
}

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 != 0) {
                left++;
            }
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}