剑指Offer（一）：二维数组中的查找
//二分查找
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; } }
剑指Offer（六）：旋转数组的最小数字
//参考剑指offer ，将数组分为两个子数组
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]; } }
剑指Offer（十三）：调整数组顺序使奇数位于偶数前面
//两个数组，时间换空间
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; } }
