java软件工程师面试宝典7.4-输出几个数字所有不同的排列顺序
java程序员面试宝典7.4--输出几个数字所有不同的排列顺序
额。。刚才用错标签了貌似
你自己运行一下吧。。反正我运行的时候是没有的
你自己运行一下吧。。反正我运行的时候是没有的
12234 // 12243 // 12324 // 12342 // 12423 // 12432 // 13224 // 13242 // 13422 // 14223 // 14232 // 14322 // 21234 // 21243 // 21324 // 21342 // 21423 // 21432 // 22134 // 22143 // 22314 // 22341 // 22413 // 22431 // 23124 // 23142 // 23214 // 23241 // 23412 // 23421 // 24123 // 24132 // 24213 // 24231 // 24312 // 24321 // 31224 // 31242 // 31422 // 32124 // 32142 // 32214 // 32241 // 32412 // 32421 // 34122 // 34212 // 34221 // 41223 // 41232 // 41322 // 42123 // 42132 // 42213 // 42231 // 42312 // 42321 // 43122 // 43212 // 43221 // 这是我运行之后的结果
你自己运行一下吧。。反正我运行的时候是没有的
12234 // 12243 // 12324 // 12342 // 12423 // 12432 // 13224 // 13242 // 13422 // 14223 // 14232 // 14322 // 21234 // 21243 // 21324 // 21342 // 21423 // 21432 // 22134 // 22143 // 22314 // 22341 // 22413 // 22431 // 23124 // 23142 // 23214 // 23241 // 23412 // 23421 // 24123 // 24132 // 24213 // 24231 // 24312 // 24321 // 31224 // 31242 // 31422 // 32124 // 32142 // 32214 // 32241 // 32412 // 32421 // 34122 // 34212 // 34221 // 41223 // 41232 // 41322 // 42123 // 42132 // 42213 // 42231 // 42312 // 42321 // 43122 // 43212 // 43221 // 这是我运行之后的结果
哦，不好意思，我理解错了，我以为是把相同的数字的重复去掉呢。。
/**
* 无重复全排列问题
* 输出1,2,2,3,4这几个数字所有不同的排列顺序
* 一个递归问题，想法是如果当前数字确定下来，后面的几位还有几种组合方式，逐步的缩小后面几位的规模
*
* 输出的完整性问题：定义一个result专门装前面排序好的元素，input里装的是后面顺序没有定下来的元素的集合，
* layer是表示当前处理的是input中的第几位，每次input为空的时候，都把result里的元素都打印一下
*
*无重复问题：如果在这个layer上，已经处理过一个跟当前元素值相同的元素，就把这个元素跳过去
* @author justrun
*
*/
public class plus {
public static void main(String args[]){
List<Integer> input = new LinkedList<Integer>();
input.add(1);
input.add(2);
input.add(2);
input.add(3);
input.add(4);
int[] result = new int[input.size()];
print(input,0,result);
}
public static void print(List<Integer> input, int layer, int[] result){
if(input.isEmpty()){ //后面没排序的元素集合为空，输出一次result集合
for(int i=0 ; i<5; i++){
System.out.print(result[i]);
}
System.out.println("");
return;
}
int flag;
for(int i = 0 ; i<input.size() ; i++){
int node = (Integer)input.get(i);
flag = 0; //同一位置，重复的数字只调用一次
for(int n=0 ; n<i; n++){
if( node == (Integer)input.get(n)){
flag = 1;
break;
}
}
if(flag == 0){
result[layer]=node;
List<Integer> newRefer = new LinkedList<Integer>();
for(int j=0 ; j<input.size() ; j++){
newRefer.add((Integer) input.get(j));
}
newRefer.remove(i); //深拷贝一个新的input集合，把正在处理的元素，从当前的input集合中拿掉
print(newRefer,layer+1,result);
}
}
}
1 楼
wkshippou
2012-09-02
niubility
2 楼
巴巴米
2012-09-02
你的消除重复应该没成功吧。。而且我觉得先消除重复在排序可能更快点
不过感觉这么做数据一大的话就会很慢
package test.integer;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Plusplus {
public static void main(String args[]) {
List<Integer> result = new ArrayList<Integer>();
List<Integer> input = new ArrayList<Integer>();
input.add(1);
input.add(2);
input.add(2);
input.add(3);
input.add(4);
Set<Integer> set = new HashSet<Integer>(input) ;
input.clear();
input.addAll(set) ;
print(input,result) ;
}
public static void print(List<Integer> input,List<Integer> result) {
for(int i = 0 ; i < input.size() ;i++) {
List<Integer> tempresult = new ArrayList<Integer>() ;
tempresult.addAll(result) ;
List<Integer> temp = new ArrayList<Integer>() ;
temp.addAll(input) ;
if(temp.size()==1) {
tempresult.add(temp.get(0));
System.out.println(tempresult);
} else {
tempresult.add(temp.get(i));
temp.remove(i) ;
print(temp,tempresult) ;
}
}
}
}
不过感觉这么做数据一大的话就会很慢
3 楼
巴巴米
2012-09-02
public class Plusplus {
public static void main(String args[]) {
List<Integer> result = new ArrayList<Integer>();
List<Integer> input = new ArrayList<Integer>();
input.add(1);
input.add(2);
input.add(2);
input.add(3);
input.add(4);
Set<Integer> set = new HashSet<Integer>(input) ;
input.clear();
input.addAll(set) ;
print(input,result) ;
}
public static void print(List<Integer> input,List<Integer> result) {
for(int i = 0 ; i < input.size() ;i++) {
List<Integer> tempresult = new ArrayList<Integer>() ;
tempresult.addAll(result) ;
List<Integer> temp = new ArrayList<Integer>() ;
temp.addAll(input) ;
if(temp.size()==1) {
tempresult.add(temp.get(0));
System.out.println(tempresult);
} else {
tempresult.add(temp.get(i));
temp.remove(i) ;
print(temp,tempresult) ;
}
}
}
}
额。。刚才用错标签了貌似
4 楼
巴巴米
2012-09-02
晕死。。就这样吧。。不知道怎么回事
5 楼
Iam42
2012-09-02
巴巴米 写道
晕死。。就这样吧。。不知道怎么回事
已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么
6 楼
巴巴米
2012-09-02
Iam42 写道
巴巴米 写道
晕死。。就这样吧。。不知道怎么回事
已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么你自己运行一下吧。。反正我运行的时候是没有的
7 楼
Iam42
2012-09-02
巴巴米 写道
Iam42 写道
巴巴米 写道
晕死。。就这样吧。。不知道怎么回事
已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么你自己运行一下吧。。反正我运行的时候是没有的
12234 // 12243 // 12324 // 12342 // 12423 // 12432 // 13224 // 13242 // 13422 // 14223 // 14232 // 14322 // 21234 // 21243 // 21324 // 21342 // 21423 // 21432 // 22134 // 22143 // 22314 // 22341 // 22413 // 22431 // 23124 // 23142 // 23214 // 23241 // 23412 // 23421 // 24123 // 24132 // 24213 // 24231 // 24312 // 24321 // 31224 // 31242 // 31422 // 32124 // 32142 // 32214 // 32241 // 32412 // 32421 // 34122 // 34212 // 34221 // 41223 // 41232 // 41322 // 42123 // 42132 // 42213 // 42231 // 42312 // 42321 // 43122 // 43212 // 43221 // 这是我运行之后的结果
8 楼
巴巴米
2012-09-02
Iam42 写道
巴巴米 写道
Iam42 写道
巴巴米 写道
晕死。。就这样吧。。不知道怎么回事
已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么你自己运行一下吧。。反正我运行的时候是没有的
12234 // 12243 // 12324 // 12342 // 12423 // 12432 // 13224 // 13242 // 13422 // 14223 // 14232 // 14322 // 21234 // 21243 // 21324 // 21342 // 21423 // 21432 // 22134 // 22143 // 22314 // 22341 // 22413 // 22431 // 23124 // 23142 // 23214 // 23241 // 23412 // 23421 // 24123 // 24132 // 24213 // 24231 // 24312 // 24321 // 31224 // 31242 // 31422 // 32124 // 32142 // 32214 // 32241 // 32412 // 32421 // 34122 // 34212 // 34221 // 41223 // 41232 // 41322 // 42123 // 42132 // 42213 // 42231 // 42312 // 42321 // 43122 // 43212 // 43221 // 这是我运行之后的结果
哦，不好意思，我理解错了，我以为是把相同的数字的重复去掉呢。。
9 楼
thihy
2012-09-02
面试时，还是非递归实现更加好一点。
10 楼
metaphy
2012-09-02
使用HashMap来存储，可以去掉关于flag的那一段
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class PlusTriple {
private static HashMap<String, Integer> resultMap = new HashMap<String, Integer>();
public static void main(String args[]) {
List<Integer> input = new LinkedList<Integer>();
input.add(1);
input.add(2);
input.add(2);
input.add(3);
input.add(4);
int[] result = new int[input.size()];
fullArray(input, 0, result);
// 打印结果
Set<String> results = resultMap.keySet();
Iterator<String> it = results.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
public static void fullArray(List<Integer> input, int layer, int[] result) {
if (input.isEmpty()) { // 后面没排序的元素集合为空，输出一次result集合
StringBuffer ss = new StringBuffer();
for (int i = 0; i < 5; i++) {
ss.append(result[i]);
}
if (!resultMap.containsKey(ss.toString())) {
resultMap.put(ss.toString(), 1);
}
return;
}
for (int i = 0; i < input.size(); i++) {
result[layer] = input.get(i);
List<Integer> newRefer = new LinkedList<Integer>();
for (int j = 0; j < input.size(); j++) {
newRefer.add(input.get(j));
}
newRefer.remove(i); // 深拷贝一个新的input集合，把正在处理的元素，从当前的input集合中拿掉
fullArray(newRefer, layer + 1, result);
}
}
}