剑指offer（九）

27. 字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路：一个n位字符串，第一位与后面每一位交换位置，可以得到n个字符串；将这n个字符串的第一位固定，后面n-1位视作新的字符串，重复上面的交换操作。所得的所有字符串就是这个n位字符串的全排列。这里要注意的是，当字符串中的某两位相同时，不作交换。

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    private ArrayList<String> res = new ArrayList<String>();
    

    public void swap(char[] c, int i , int j){
        char tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }
    
    public void generatePermutation(char[] c, int i){
        if(i == c.length -1) res.add(String.valueOf(c));
        for(int j = i; j < c.length; j++){
            if(i == j || c[i] != c[j]){
                swap(c, i, j);
                generatePermutation(c, i+1);
                swap(c, i ,j);
            }
        }
    }
    
    public ArrayList<String> Permutation(String str) {
        if(str.length() == 0) return res;
        char[] c = str.toCharArray();
        generatePermutation(c, 0);
        Collections.sort(res);
        return res;
    }
}

28. 数组中出现过次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路： 用快排思想，parition可以用来找到数组中的第k大的数字，因此也可以用来找中位数。即当k在mid左侧的时候，partion(array, k + 1, len -1)；在右侧的时候partition(array, 0, k -1)。找到中位数之后验证一下是否多于半数即可。

public class Solution {
    public int partition(int n[], int left, int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

    public int MoreThanHalfNum_Solution(int [] array) {
        int count = 0, len = array.length;
        int left = partition(array, 0, len - 1);
        while (left != len/2){
            if(left < len/2) left = partition(array, left + 1, len - 1);
            else left = partition(array, 0, left - 1);
        }
        int num = array[left];
        for(int j = 0; j < array.length; j++){
            if(array[j] == num) count++;
        }
        return count > array.length/2?num:0;
    }
}

29. 最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路： 利用快排partition思想，在数组中找到第k个数字，此时的原数组k左侧的数就是最小的K个数。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k > input.length || k == 0 || k <= 0) return res;
        int num = partition(input, 0, input.length - 1);

        while(num != (k - 1)){
            if(k - 1 < num) num = partition(input, 0, num - 1);
            else if (k - 1> num) num = partition(input, num + 1, input.length - 1);
        }
        for(int i = 0; i < k; i++){
            res.add(input[i]);
        }
        return res;
    }
    public int partition(int[] n, int left, int right){
        int pivot = n[left];
        while(left != right){
            while(left < right && n[right] >= pivot) right--;
            if(left < right) n[left++] = n[right];
            while(left < right && n[left] <= pivot) left++;
            if(left < right) n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }
}