[java] view plain copy
package com.bzu.converter;
import java.util.Scanner;
/**
* 思路壹：采用字符串的方式實現
*/
public class JianFanConvert1 {
public static final String jianti = "萬與醜專業叢東絲";
public static final String fanti = "萬與醜專業叢東絲";
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("請輸入妳想轉換的句子");
String words = input.next();
for (int i = 0; i < words.length(); i++) {
char tempChar = words.charAt(i);
int position = jianti.indexOf(tempChar);//此方法調用時間復雜度為O(n)
char fantiChar;
if (position == -1) {
fantiChar = tempChar;
} else {
fantiChar = fanti.charAt(position);
}
System.out.print(fantiChar);
}
}
}
分析上述實現，時間復雜度為O(n*n)，當問題規模擴大時會非常耗時。
實現思路二：采用哈希算法實現
1.哈希方法
哈希方法在就是在鍵和值之間建立壹個確定的對應函數關系hash()，就是key向value的換算關系，使得每壹個鍵與結構中的壹個唯壹的存儲位置相對應：值的存儲位置=hash(鍵)即Value的位置=hash(key)
例如有壹組“鍵值對”：、、、、，我們按照如下哈希函數對鍵進行計算:hash(x)=x%17+3，得出如下結果：hash(5)=8、hash(8)=11、hash(12)=15、hash(17)=3、hash(20)=6。
我們把、、、、分別放到地址為8、11、15、3、6的位置上。當要檢索17對應的值的時候，只要首先計算17的哈希值為3，然後到地址為3的地方去取數據就可以找到17對應的數據是“Lily”了。
使用哈希方法，查詢的時間復雜度為O(1)，能夠直接定位其位置，大大加快數據的查詢速度。
2.哈希表
將數據采用哈希算法進行保存的數據結構就是哈希表，常見操作put、get、remove。
Java中的HashMap使用（Java內置的哈希表數據結構）
HashMap的主要方法
int size()：得到Map中“鍵-值對”的數量
boolean isEmpty()：Map是否是空的，也就是是否不含有任何“鍵-值對”
boolean containsKey(Object key)：Map中是否含有以key為鍵的“鍵-值對”
boolean containsValue(Object value)：Map中是否含有以value為值的“鍵-值對”
Object get(Object key)：從Map中得到以key為鍵的值，如果Map中不含有以key為鍵的“鍵-值對”則返回null
Object put(Object key, Object value)：向Map中存儲以key為鍵、value為值的“鍵-值對”
Object remove(Object key):從Map中移除以key為鍵的“鍵-值對”
void clear()：清除所有“鍵-值對”
Set keySet()：得到所有的鍵
Collection values()：得到所有的值
Set entrySet()：得到所有的“鍵-值對”，Set中的類型是Map.Entry
[java] view plain copy
package com.bzu.converter;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* 思路二：采用哈希算法實現
*/
public class JianFanConvert2 {
public static final String jianti = "萬與醜專業叢東絲";
public static final String fanti = "萬與醜專業叢東絲";
public static void main(String[] args) {
Map map=new HashMap();
for(int i=0;i<jianti.length();i++){
map.put(jianti.charAt(i),fanti.charAt(i));
}
Scanner input = new Scanner(System.in);
System.out.println("請輸入妳想轉換的句子");
String words = input.next();
/**
* 為了測試隨著問題規模的擴大用時
*/
for(int i=0;i<10;i++){
words=words+words;
}
long begin=System.currentTimeMillis();
for (int i = 0; i < words.length(); i++) {
char tempChar = words.charAt(i);
Character character=map.get(tempChar);
char fantiChar;
if (character == null) {
fantiChar = tempChar;
} else{
fantiChar=character;
}
System.out.print(fantiChar);
}
long end=System.currentTimeMillis();
System.out.println("\n用時："+(end-begin));
}
}
分析上述算法實現，時間復雜度變為o(n)
問題探討：
為什麽算法復雜度由O(n*n)變成O(n)，但是實際執行時間沒有明顯的變化？
print，數據在CPU、內存中運算都非常快，壹旦與外設（打印機、網絡（網卡）、顯示設備（顯卡））交換數據，速度就會慢很多