每日一题之《剑指offer》27,28题目

第二十七题：字符串的排列

难易度：⭐⭐⭐

输入一个字符串,按字典序打印出该字符串中字符的所有排列
例如输入字符串abc
则打印出由字符a,b,c所能排列出来的所有字符串
abc,acb,bac,bca,cab和cba。
输入描述：
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母

本题分析：
以输入的字符串为 “abc”举例：
要想求出整个字符串的排列，可以分成两步：
第一步：求出所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换
第二步：固定第一个字符，求出后面所有字符的排列

输入：abc

a和第一个位置的字符也就是自己发生交换  abc
对于a后面的字符串 bc递归这样一个过程

a和第二个位置的字符b发生交换  bac 
对于b后面的字符串ac递归这样一个过程

a和第三个位置的字符c发生交换  cba
对于c后面的字符串ba递归这样一个过程

这样求解后，得到了字符串的全排列，但是并不是按照字典序进行排序的顺序，所以还需要对所有的字符串进行排序，才可以返回结果。
本题我只想到了这样一种思路，二刷的时候，会想想有没有更好的解决办法
代码如下：

import java.util.Collections;
import java.util.ArrayList;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        
        ArrayList<String> arrayList = new ArrayList<>();
        
        if(str.length() == 1){
            arrayList.add(str);
            return arrayList;
        }
        
        for(int i = 0; i < str.length(); i++){
            if(i == 0 || str.charAt(i) != str.charAt(0)){
                String temp = swap(str,0,i);
                String childStr = temp.substring(1);
                ArrayList<String> tempList = Permutation(childStr);
                for(String s : tempList){
                    arrayList.add(temp.charAt(0) + s);
                }
            }
        }
        Collections.sort(arrayList);
        return arrayList;
    }

    public static String swap(String str,int i,int j){
        if(i == j){
            return str;
        }
        char tempI = str.charAt(i);
        char tempJ = str.charAt(j);
        StringBuilder sb = new StringBuilder(str);
        sb.setCharAt(i,tempJ);
        sb.setCharAt(j,tempI);
        return sb.toString();
    }
}

第二十八题：数组中出现次数超过一半的数字

难易度：⭐

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

本题虽然非常简单，但是我觉得这道题真的非常好。
先说一下，我看到这道题目最先想到的思路吧：

思路一：

不难想到，利用HashMap,遍历一遍数组以后，key存数组的值，value存，这个值在数组中出现的个数，在更新value的时候，取判断当前的value是否超过了arr.length/2。当然，这种思路是我未加思考的结果，还是把代码奉上，任凭大家吐槽：

import java.util.HashMap;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < array.length;i++){
            if(map.containsKey(array[i])){
                int temp = map.get(array[i]);
                map.put(array[i],++temp);
                if(isMoreThanHalf(array,temp)){
                    return array[i];
                }
            }else{
                map.put(array[i],1);
                if(isMoreThanHalf(array,map.get(array[i]))){
                    return array[i];
                }
            }
        }
        return 0;
    }
    
    public static boolean isMoreThanHalf(int[] arr,int num){
        return num > arr.length >> 1;
    }
}

思路二：

上面的代码使用了多余的数据结构HashMap,如何能够不使用任何数据结构，仅在O(n)的时间复杂度下完成这样的需求呢？
仔细想一想：
一个数组中，一个数字出现的次数如果超过数组长度的一半，那么经过排序后，这个数字一定位于数组的中间
如,对于数组：

1,1,3,1,5

排序后：

1,1,1,3,5

1出现的次数为3 超过了数组长度的一半 2，那么排序后的这个数一定会在数组的最中间！
有了这样一个结论，我们不难写出代码：

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        Arrays.sort(array);
        int target = array[array.length >> 1];
        int count = 0;
        for(int i = 0;i < array.length; i++){
            if(array[i] == target){
                count++;
                if(isMoreThanHalf(count,array)){
                    return target;
                }
            }
        }
        return isMoreThanHalf(count,array)? target:0;
    }
    public static boolean isMoreThanHalf(int count,int[] array){
        return count > array.length >> 1;
    }
}

但是，这样做又会强行将算法变为O(nlogn)的时间复杂度，本题的最优解应该是O(n)级别的算法：
本思路是我在牛客网本题下的评论区看到的，觉得非常妙：

思路三：

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多
采用阵地攻守的思想：
第一个数字作为第一个士兵，守阵地 count = 1;
遇到相同元素，则count++;
遇到不同的元素，即为敌人，同归于尽，count--;
又以新的i值作为守阵地的士兵继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一般即可

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int target = array[0];
        int count = 1;
        for(int i = 1;i < array.length;i++){
            if(count == 0){
                target = array[i];
                count = 1;
            }else if(array[i] == target){
                count++;
            }else{
                count--;
            }
        }
        count = 0;
        for(int i = 0;i < array.length;i++){
            if(array[i] == target){
                count++;
            }
        }
        return count > array.length >> 1 ? target : 0;
    }
}