《剑指offer》– 调整数组顺序使奇数位于偶数前面、顺时针打印矩阵、数字在排序数组中出现的次数

一、调整数组顺序使奇数位于偶数前面：

1、题目：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变

2、解决思路：

如果题目中没有要求偶数和偶数、奇数和奇数之间的相对位置不变，这道题就比较简单，我们只需维护两个指针：第一个指针pHead 初始化为数组的第一个元素，第二个指针pTail 初始化为数组的最后一个元素。根据题目要求:所有奇数位于数组的前半部分，偶数位于数组的后半部分；我们只需：

①使指针pHead 向后遍历，直到指向的整数为偶数；

②使指针pTail 向前遍历，直到指向的整数为奇数；

③交换指针pHead 和指针pTail 所指向的元素。

④在 pHead 和 pTail 相遇之前，pHead继续向后遍历，pTail继续向前遍历。

回归本题：

（1）本题第一种解决方法：

用空间换时间的做法，new一个数组，从头开始遍历，遇到偶数保存进新数组，并且删除原先的偶数，最后将偶数部分接在奇数部分之后。（在这里就不贴代码了）

（2）本题第二种解决方法：

首先寻找第一个奇数，并将其放在0号位置。然后将第一个奇数之前的元素全部往后移一位。第二步，依次在第一个奇数之后的元素中寻找奇数，找到之后，移动到第1号位置，重复第二步的步骤。就可以保证原来的相对顺序。

代码实现：

	public void reOrderArray(int [] array) {
	        
		int firstIndex=0;//记录第一个奇数的位置
		int lastIndex=0;//记录排好序的奇数的最后一个位置
		
		for(int i=0;i<array.length;i++){
			if(array[i]%2==1){
				//找到第一个奇数
				int temp=array[i];
				int ti=i;
				for(;ti>0;ti--){
					array[ti]=array[ti-1];//将第一个奇数之前的所有元素往后移动一个位置
				}
				array[0]=temp;//将第一个奇数放到array[0]位置
				
				firstIndex=i;
				break;
			}
		}
		
		for(++firstIndex;firstIndex<array.length;firstIndex++){//依次寻找剩余的奇数
			if(array[firstIndex]%2==1){
				int temp=array[firstIndex];
				int tj=firstIndex;
				for(;tj>lastIndex;tj--){
					array[tj]=array[tj-1];
				}
				array[++lastIndex]=temp;
			}
		}
		
	}

（3）本题第三种解决方法：

个人觉得第三种方式是比较好的一种。

从数组中寻找第一个偶数，每当找到前面的偶数和偶数后面的第一个奇数之后，那么把之间的部分（包括那个偶数）统一后移一位， 因为之间的都是偶数，这样把提前保存起来的那个奇数放到前边空出来的那一位。这样相当于132457把5移动到2 4这两个偶数的前面，1和5本来就是前后顺序的。这样堡整理调整之后的奇偶各自的相对顺序不会变。

代码实现：

public class Solution {
	public void reOrderArray(int [] array) {
        int jishuIndex=0;//偶数后面的第一个奇数的下标
        int oushuIndex=0;//偶数的下标
		int temp = 0;
		
		while(jishuIndex<array.length && oushuIndex < array.length){
			
			//寻找第一个偶数的位置
			while(oushuIndex<array.length){
				if(array[oushuIndex]%2==0){
					break;
				}
				oushuIndex++;
			}
			
			//寻找偶数后面的第一个奇数：
			jishuIndex=oushuIndex+1;
			while(jishuIndex<array.length){
				if(array[jishuIndex]%2!=0){
					temp=array[jishuIndex];
					break;
				}
				jishuIndex++;
			}
			
			//将奇数放到第一个偶数的位置，偶数都往后面移动一格
			if(jishuIndex<array.length){
				for(int i=jishuIndex;i>oushuIndex;i--){
					array[i]=array[i-1];
				}
				array[oushuIndex]=temp;
			}else{
				break;
			}
		}
    }
}

二、顺时针打印矩阵：

1、题目：

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

2、解题思路：

参考这篇博客：https://blog.csdn.net/yanxiaolx/article/details/52254590。

由于题目是以从外圈到内圈的顺序依次打印，在矩阵中标注一圈作为分析的目标。设矩阵的宽度为cols，而其高度为rows。选取左上角坐标为(startX, startY)，右下角坐标为(endX, endY)的一个圈来分析。

由于endX和endY可以根据startX、startY以及columns、rows来求得，因此此时我们只需要引入startX和startY两个变量。我们可以想象有一个循环，在每一次循环里我们从(startX, startY)出发按照顺时针打印数字。

接着分析这个循环结束的条件。对一个5×5的矩阵而言，最后一圈只有一个数字，对应的坐标为(2, 2)。我们发现5 > 2 * 2。对一个6×6的矩阵而言，最后一圈有四个数字，对应的坐标仍然为(2, 2)。我们发现6 > 2 * 2依然成立。于是我们可以得出，让循环继续的条件是“cols > startX * 2 && rows > startY * 2”。

接下来我们分析如何按照顺时针的顺序打印一圈的数字。我们可以分四步来打印：第一步是从左到右打印一行，第二步是从上到下打印一列，第三步从右到左打印一行，最后一步是从下到上打印一列。也就是我们把打印一圈数字这个问题，分解成四个子问题。

值得注意的是，最后一圈可能退化成只有一行、只有一列、甚至只有一个数字，因此打印这样的一圈就不需要四步了。

3、实现代码：

import java.util.ArrayList;
public class Solution {
    
    public ArrayList<Integer> printMatrix(int [][] matrix) {
      if(matrix==null)
          return null;
        
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        int start =0;
        while(matrix[0].length>start*2 && matrix.length>start*2){
            printOneCircle(arrayList,matrix,start);
            start++;
        }
        
        return arrayList;
    }
    
    public void printOneCircle(ArrayList<Integer> arrayList,int [][] array,int start){
        int columns=array[0].length;
        int rows=array.length;
        int endX=columns-1-start;
        int endY=rows-1-start;
        
        //从左到右打印一行，不需要判断
        for(int i=start;i<=endX;i++){
            int number = array[start][i];
            arrayList.add(number);
        }
        
        //从上到下打印一列数据
        if(start<endY){
            for(int i=start+1;i<=endY;i++){
                int number = array[i][endX];
                arrayList.add(number);
            }
        }
        
        //从右到左打印一行数据
        if(start<endX && start<endY){
            for(int i=endX-1;i>=start;i--){
                int number = array[endY][i];
                arrayList.add(number);
            }
        }
        
        //从下到上打印一列
        if(start<endX && start <endY-1){
            for(int i= endY-1;i>=start+1;i--){
                int number= array[i][start];
                arrayList.add(number);
            }
        }
    }
}

三、数字在排序数组中出现的次数：

1、题目：

统计一个数字在排序数组中出现的次数。

2、解题思路：

因为array中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5，这两个数应该插入的位置，然后相减即可。

3、代码实现：

public class Test2 {
	
	public int GetNumberOfK(int [] array , int k) {
		return biSearch(array,k+0.5)-biSearch(array,k-0.5);
    }
	
	private int biSearch(int[] array,double num){
		
		int start=0;
		int end=array.length-1;
		
		while(start<=end){
			int mid = (end-start)/2+start;
			if(array[mid]>num){
				end=mid-1;
			}else if(array[mid]<num){
				start=mid+1;
			}
		}
		return start;
	}
}