每日一题之《剑指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;
}
}
查看36道真题和解析