快速找出两个字符串中所有相同的字符

面试时看到一个试题, 编写算法, 快速找出两个字符串中所有相同的字符. 现实现如下:

1. 利用TreeSet来查找是否有相同的字符（之前是利用TreeSet来查找）

2. 利用HashSet来查找是否有相同的字符（改进后利用HashSet来查找）

经测试，HashSet几乎在所有情况下都比TreeSet耗时更少。HashSet的底层实现决定了其能比TreeSet更快速的处理该问题。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.HashSet;
import java.util.TreeSet;

public class CharFilter {

	// 利用TreeSet进行 查找
	public static void filterByTreeSet(String str1, String str2, Collection<Character> result) {
		// 利用Java的TreeSet进行排序
		TreeSet<Character> tree1 = new TreeSet<Character>();
		for (char ch : str1.toCharArray()) {
			tree1.add(ch);
		}

		// 结果集
		for (char ch : str2.toCharArray()) {
			// 查找相同的字符
			boolean contain = tree1.contains(ch);
			if (contain) {
				// 加入结果集
				result.add(ch);
			}
		}
	}
	
	// 利用HashSet进行 查找
	public static void filterByHashSet(String str1, String str2, Collection<Character> result) {
		// 利用Java的TreeSet进行排序
		HashSet<Character> tree1 = new HashSet<Character>();
		for (char ch : str1.toCharArray()) {
			tree1.add(ch);
		}

		// 结果集
		for (char ch : str2.toCharArray()) {
			// 查找相同的字符
			boolean contain = tree1.contains(ch);
			if (contain) {
				// 加入结果集
				result.add(ch);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		// 输入流
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		// 输入第一个字符串
		System.out.println("Please input string 1");
		String str1 = reader.readLine();

		// 输入第二个字符串
		System.out.println("Please input string 2");
		String str2 = reader.readLine();

		// 利用Java的TreeSet进行排序
		TreeSet<Character> result = new TreeSet<Character>();
		
		long start, end;
		long treeGap, hashGap;
		
		start = System.currentTimeMillis();
		for (int i = 0; i < 500000; i++) {
			filterByTreeSet(str1, str2, result);
		}
		end = System.currentTimeMillis();
		treeGap = end - start;

		// 输出相同的字符
		System.out.println("耗时: " + treeGap);
		System.out.println("相同的字符数: " + result.size());
		for (char ch : result) {
			System.out.print(ch + " ");
		}
		
		result.clear();
		start = System.currentTimeMillis();
		for (int i = 0; i < 500000; i++) {
			filterByHashSet(str1, str2, result);
		}
		end = System.currentTimeMillis();
		hashGap = end - start;
		
		// 输出相同的字符
		System.out.println();
		System.out.println("耗时: " + hashGap);
		System.out.println("相同的字符数: " + result.size());
		for (char ch : result) {
			System.out.print(ch + " ");
		}
	}

}


测试输出：
Please input string 1面试时看到一个试题, 编写算法, 快速找出两个字符串中所有相同的字符. 现实现如下:Please input string 2经测试，HashSet几乎在所有情况下都比TreeSet耗时更少。HashSet的底层实现决定了其能比TreeSet更快速的处理该问题。耗时: 1576相同的字符数: 11下 实 快 所 时 有 现 的 试 速 题 耗时: 949相同的字符数: 11下 实 快 所 时 有 现 的 试 速 题 


转载自原文链接, 如需删除请联系管理员。 
原文链接：快速找出两个字符串中所有相同的字符，转载请注明来源！
				

		

    			赞 
        0
    			
		
		

			　分享到：