解析、查找數組中重複出現的元素（Java）



解析、查找數組中重複出現的元素，Java實作。

《資料結構與算法分析：解析、查找數組中重複出現的元素》

問題描述：一個結構化資料，假設事先按照某種順序排好序（比如升序）的一個數組中，無規則、重複出現若幹次某個相同元素，形如有序數組data：

data = {  "A", "A", "B", "C", "C", "D", "D" , "D"  }

data數組中，事先已經按照 A -> Z 升序排好，但是數組内部的資料元素無規則重複出現：

’A’在數組位置0,1（注：0,1指下标，下同）重複出現兩次；

’B’沒有重複；

’C’在數組位置3,4重複出現兩次；

’D’在5,6,7位置重複出現三次。

針對這樣的資料結構，設計算法并代碼實作查找、分析數組中重複出現的元素。

算法的應用場景：這種算法的應用場景之一就是在通訊錄聯系人的操作中将被涉及。比如在我之前寫的一篇文章：《Android基于PinnedSectionListView實作聯系人通訊錄》（連結位址：

http://blog.csdn.net/zhangphil/article/details/47271741

，此文涉及到通訊錄分類整理，需要按照聯系人姓氏的首字元排序分組）。通常，一個手機的通訊錄中存有若幹個聯系人，每個聯系人都有姓，如果按照姓氏的首字元（比如，中文姓’張’，Zhang，首字元為’Z’）排成升序，将構成形如上述data數組的資料結構，進而對聯系人進行分組。比如，都是張姓聯系人，則都歸入到’Z’組下，進而便于使用者快速定位查找通訊錄中個某一張姓聯系人。是以，将此現實中的應用場景建立資料模型，就是本文算法所要解決的計算問題。

現給出一個代碼實作（Java）的算法：

import java.util.ArrayList;

public class Test {

	// 原始資料data。假設data數組中的資料元素已經按照某種順序排好。
	// 但是，該數組中的資料元素重複出現。
	// 我們的目的是查找、解析data數組中重複出現的某元素。
	// 比如，在這個data數組中，元素'C'在數組位置2,3重複出現兩次。
	// 注意！有些元素沒有重複出現，比如元素'B'。
	private String[] data = { "A", "A", "B", "C", "C", "D", "D", "D" };

	// 存儲分類好的資料元素。
	private ArrayList<Group> groups = new ArrayList<Group>();

	// 核心的算法實作。
	public void find() {

		// 遊标index
		int index = 0, j = 0;

		while (index < data.length) {
			Group group = new Group();
			group.title = data[index];
			
			String t = group.title;

			ArrayList<String> children = new ArrayList<String>();

			for (j = index; j < data.length; j++) {

				String child = data[j];
				if (t.equals(child)) {
					// 同時記錄該重複出現的元素在原數組中的下标j，便于查驗、評估結果。
					children.add(child + "@" + j);
				} else {
					break;
				}
			}

			// 往後推進遊标index
			index = j;

			group.children = children;
			groups.add(group);
		}
	}

	// 輸出結果。
	private void print() {
		for (int i = 0; i < groups.size(); i++) {
			Group g = groups.get(i);
			System.out.println(g);
		}
	}

	// 自己構造一個類，作為一組資料的容器。
	// 該類用一個title表明這一group資料是歸屬于那個重複元素的組。
	// 該title下重複的元素裝入到ArrayList<String> children中，供周遊查詢。
	private class Group {
		public String title;
		public ArrayList<String> children;

		// 結果。
		@Override
		public String toString() {
			String str = "組" + title + ": ";
			for (int i = 0; i < children.size(); i++) {
				str += children.get(i) + " ";
			}

			return str;
		}
	}

	public static void main(String args[]) {
		Test t = new Test();
		t.find();
		t.print();
	}
}           

結果輸出：

組A: A@0 A@1 
組B: B@2 
組C: C@3 C@4 
組D: D@5 D@6 D@7