解析、查找数组中重复出现的元素（Java）

红太狼 2023-10-16 22:02 10阅读 0赞

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

[http_blog.csdn.net_zhangphil_article_details_47271741]: http://blog.csdn.net/zhangphil/article/details/47271741