java程序员面试宝典7.4--输出几个数字所有不同的排列顺序 -

Iam42

浏览: 275479 次
性别:
来自: 北京

最近访客更多访客>>

songzhihuis

c303437571

裴喜龙

jahentao

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

java程序员面试宝典7.4--输出几个数字所有不同的排列顺序

博客分类：

算法

/**
 * 无重复全排列问题
 * 输出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
顶

3
踩

分享到：

云计算虚拟交换技术思路整理 | 编程之美-3.11

2012-09-02 11:26
浏览 4098
评论(10)
分类:编程语言
查看更多

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);
		}
	}
}

9 楼 thihy 2012-09-02

面试时，还是非递归实现更加好一点。

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 // 这是我运行之后的结果

哦，不好意思，我理解错了，我以为是把相同的数字的重复去掉呢。。

7 楼 Iam42 2012-09-02

巴巴米写道

Iam42 写道

巴巴米写道

晕死。。就这样吧。。不知道怎么回事

已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么

你自己运行一下吧。。反正我运行的时候是没有的

6 楼巴巴米 2012-09-02

Iam42 写道

巴巴米写道

晕死。。就这样吧。。不知道怎么回事

已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么

你自己运行一下吧。。反正我运行的时候是没有的

5 楼 Iam42 2012-09-02

巴巴米写道

晕死。。就这样吧。。不知道怎么回事

已经消除了重复，只有在找到没有重复的元素的时候才会调用递归，但是这个算法确实感觉不是最优的，你有什么改进的办法么

4 楼巴巴米 2012-09-02

晕死。。就这样吧。。不知道怎么回事

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) ;
			}
			
		}
		
	}
}

额。。刚才用错标签了貌似

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) ;
			}
			
		}
		
	}
}

不过感觉这么做数据一大的话就会很慢

1 楼 wkshippou 2012-09-02

niubility

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

java程序员面试宝典7.4--输出几个数字所有不同的排列顺序

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

java程序员面试宝典7.4--输出几个数字所有不同的排列顺序

评论

发表评论

相关推荐

KMP算法【转】

排序方法的选择

给定出栈序列和入栈序列，求出栈入栈顺序

如何判断一个分数是否能化成非循环小数

蓄水池抽样算法

编程之美2.3-发帖水王扩展问题

编程之美-3.11

最近访客更多访客>>