解析、查找数组中重复出现的元素(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 

上一篇:美国网络司令部133支网络部队已拥有初步作战能力


下一篇:关于解决JQUERY对INPUT元素Change事件不兼容的问题