解析、查找数组中重复出现的元素(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: [email protected] [email protected]
组B: [email protected]
组C: [email protected] [email protected]
组D: [email protected] [email protected] [email protected]

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-02

解析、查找数组中重复出现的元素(Java)的相关文章

去掉有序数组中重复数字 原地 leetcode java (最简单的方法)

1.利用荷兰国旗的思路,每次记住最后一个位置,遇到一个不重复的数,放在它后面,代码很简单. Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with consta

查找数组中重复的数字

题目来源于<剑指Offer>中的面试题3:找出数组中重复的数字. // 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内.数组中某些数字是重复的,但不知道有几个数字重复了, // 也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如,如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}, // 那么对应的输出是重复的数字2或者3. 解决方法有多种,包括数组排序,哈希表法,以及作者推荐的重排数组法.此处介绍自己的一个做法,以空间换时间,通过新建数组来实现快速查

查找数组中重复项的index

var ary = [5, 4, 4, 2, 7, 8, 33, 2222, 99, 88]; function isRepeat(arr) { var hash = {}; for (var i=0,len=arr.length;i<len;i++) { if (typeof hash[arr[i]]=='undefined') { hash[arr[i]] = i; } else { console.log(i,hash[arr[i]]); } } return false; } isRep

JS数组常用函数以及查找数组中是否有重复元素的三种常用方法

阅读目录: DS01:常用的查找数组中是否有重复元素的三种方法 DS02:常用的JS函数集锦 DS01.常用的查找数组中是否有重复元素的三种方法 1. 1 var ary = new Array("111","22","33","111"); 2 var s = ary.join(",")+","; 3 for(var i=0;i<ary.length;i++) { 4 if(s.

程序员面试题目总结--数组(三)【旋转数组的最小数字、旋转数组中查找指定数、两个排序数组所有元素中间值、数组中重复次数最多的数、数组中出现次数超过一半的数】

转!http://blog.csdn.net/dabusideqiang/article/details/38271661 11.求旋转数组的最小数字 题目:输入一个排好序的数组的一个旋转,输出旋转数组的最小元素. 分析:数组的旋转:把一个数组最开始的若干个元素搬到数组的末尾.例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1.这道题最直观的解法并不难.从头到尾遍历数组一次,就能找出最小的元素,时间复杂度显然是O(N).但这个思路没有利用输入数组

【前端小小白的学习之路】----&gt;用JS编写一个函数,返回数组中重复出现过的元素

用JS编写一个函数,返回数组中重复出现过的元素,见下面的代码: var arr = [1, 2, 3, 1, 2, 3, 4, 5]; var getRepeat = function (arr) { var obj = {}; for (var i = 0, len = arr.length; i < len; i++) { if (obj[arr[i]] == undefined) { obj[arr[i]] = 1; } else { obj[arr[i]]++; } } for (var

用正则去掉数组中重复的元素

<!doctype html><html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> <script> //去掉数组中重复的元素 //此题最主要就是对数组进行排序拼接,在进行replace的替换,在进行分割,将其return到外部 //随机生成随机数压入空数组arr中 for(var i=0,arr

《数据结构、算法与应用》8.(顺序查找数组中第一个出现指定元素的位置)

最近在读<数据结构.算法与应用>这本书,把书上的习题总结一下,用自己的方法来实现了这些题,可能在效率,编码等方面存在着很多的问题,也可能是错误的实现,如果大家在看这本书的时候有更优更好的方法来实现,还请大家多多留言交流多多指正,谢谢 8. 从左至右检查数组a[0:n-1]中的元素,以查找雨x相等的那些元素.如果找到一个元素与x相等,则函数返回x第一次出现所在的位置.如果在数组中没有找到这样的元素,函数则返回-1. // // main.cpp // Test_08 // // Created

统计数组中重复元素个数

/** * 循环统计数组或集合中的重复元素个数 * @param args */ public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>(); String[] ss = {"白","黑","绿","白"}; for (int i = 0; i < ss.len