A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© obvilion 中级黑马   /  2016-9-2 09:43  /  628 人查看  /  13 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

废话不多说,内容如题;
让我们show code;
另:
测试类就不注释了,除重方法有详细注释加算法说明
[AppleScript] 纯文本查看 复制代码
package bean;
public class ArrayTool {						//声明一个类

	private ArrayTool() {}					//私有化构造函数
	public static int[] getArray(int[] arr) {		//声明一个公开的静态方法.定义其返回值类型,参数列表及方法名
		int k = 0;							//定义一个临时变量k并初始化
		int[]array = new int[arr.length];		//定义一个临时int数组用于记录信息
		array[0] = k;						//初始化其第一个元素,因为该值在算法中是固定的,不需要动态获取
		for (int i = 1;i < arr.length;i++) {		//定义外层循环用于遍历arr
			k++;							//先对k进行自增,原因在下面代码中说明
			for (int j = 0; j < i; j++) {			//定义内层循环,用于进行比对.从前往后比对和从后往前比对,并不影响算法复杂性
				if(arr[i] == arr[j]) {			//当之前的元素中找到相同元素时
					k--;					//对k进行k--运算
					break;				//并跳出当前元素的比对工作,因为找到相同的,(在这里并不需要关心重复了几次)
				}						//算法步骤将在后面给出
			}							//接10,只是因为加法比减法简单,故用加不用减,将未注释中的--算法改为++算法.
			array[i] = k;					//将k的值赋给array[i]用于记录当前元素是第几个不重复的元素
		}								//很显然若array[i-1] == array[i],这一定说明arr[i]与之前的i个元素中的某一个重复了.
		int[] result = new int[k+1];			//新建一个临时int数组用于返回不重复的值,因为k从0开始计数,所以是k+1个元素.
		int n = 0;							//新建一个临时变量用于记录录入了多少个不重复的元素
		result[0] = arr[0];					//第一个值肯定不重复,因为其找不到值进行比对
		for (int i = 1;i < arr.length;i++) {		//继续定义循环用于遍历array1,录入result;
			if (array[i] == array[i-1]) {		//之前说过,当array[i-1] == array[i],这一定说明arr[i]与之前的i个元素中的某一个重复了.
				continue;					//所以跳过本次循环
			}else {						//否则
				n++;						//n++
				result[n] = arr[i];			//将arr[i]的值赋给result[n]记录下第n+1个不重复的元素值
			}
			if (n == k) {					//当n==k时,剩下的循环就不必进行了
				break;					//所以break跳出循环
			}							//注意不能漏大括号,若按照格式写时,右大括号不是阶梯状的,那么一定有大括号漏了
		}								//或者说错位了
		return result;						//将所得结果返回之后,算法结束
	}
}										//在不计算右大括号和空行的情况下算法实现加类的声明和构造使用代码25行
/*
算法1步骤
step 1:
		得到需要进行除重的数组arr
step 2:
		对arr进行遍历
step 3:
		在遍历的同时将取得的元素与其之前的元素进行比对
step 4:
		将比对的结果用一个同样长的int类型数组记录下来 int[] array 其所记录的值就是之后将会用到的索引
step 5:
		记录方式如下:
				将第一个不重复的元素的索引记为 0 ;
				将第 i + 1 个不重复的元素的索引记为 i ;
				任意一个重复的元素的索引值将会使用其前一个元素的索引值(注:  核心思想!!!!)即用前一个索引值对其赋值;
				最后将array数组的最后一个元素记录的索引值取出并加1就是我们不重复元素的个数
		注:在这里是不需要去考虑这个重复元素 (若命名为 S) 的前一个元素是否也是重复的.因为若其前一个元素(若命名为S-1)仍旧是重
复的,其索引值仍旧是继承至S-1的前一个元素(命名为S-2)的索引值,这时S的索引值是使用S-1的,还是使用S-2的,在结果上并没有任何区
别,在数据安全性方面没有任何问题,这种舍近求远  舍本逐末的方法(即将S-2的索引值赋值给S),是不可取的,是垃圾,用不客气的话说.同
样的思路,一种体现了智慧;而另一种则是体现了ZZ.
step 6:
		建立一个新的数组,用于记录我们的结果 type[] result,,,,,,,,,arr是什么格式的数组,type[]就代表着什么格式的数组
step 7:
		根据step 5的记录原理,对result[] 用for语句将arr[]中不重复的元素录入
step 8:
		关于step 7何时结束的问题,若arr[]数组在某一项元素以后的元素都在之前的元素中出现了重复,即用array[]记录的索引值完全相同
且之后的索引值永远不再发生改变了.若还是让for循环继续进行,这种行为与step 5中使用S-2的索引值,在本质上没有区别,所以需要使用
if语句做出判断是否应当结束循环即28行中用与计数的n==k时,结束循环.
step 9:
		返回结果,结束算法
另可以通过方法重载可以对不同类型的数组进行除重运算时间关系暂时未写.
by_czs
[b]*/[/b]

[AppleScript] 纯文本查看 复制代码
//测试类
package hehe;
import java.util.Random;
import bean.ArrayTool;
public class Test {
	@SuppressWarnings("unused")
	public static void main(String[] args) {
		System.out.println("测试开始");
		Random ra = new Random();
		System.out.println("生成随机数组中...");
		long startTime = System.currentTimeMillis();
		int[] array1 = new int[1000000];
		for (int i = 0; i < 1000000; i++ ) {
			array1[i] = ra.nextInt(500000)-250000;
		}
		long endTime = System.currentTimeMillis();
		System.out.println(endTime - startTime);
		System.out.println("除重开始");
		startTime = System.currentTimeMillis();
		int[] arr1 = Array_Tool.sort(array1);
		endTime = System.currentTimeMillis();
		System.out.println(endTime - startTime);
	}
}
}
//by_czs





评分

参与人数 1黑马币 +10 收起 理由
378657357 + 10 很给力!

查看全部评分

13 个回复

正序浏览
来学习学习!!
回复 使用道具 举报
回复 使用道具 举报
嗯,我来顶帖,请给打赏
回复 使用道具 举报
回复 使用道具 举报
accomplonely 发表于 2016-9-2 20:09
这种方法只会锻炼你的思维能力,还有对数组的理解能力。很不错的

谢谢
回复 使用道具 举报
水月灬清影 发表于 2016-9-2 19:47
呵,这就有意思了,怎么我用了新特性就叫失去创新的动力了?这到底是跟紧创新脚步还是因循守旧?
首先, ...

抱歉,可能我的话有些伤人了.
但是我始终坚持一点是算法思维是无关于版本的;
另外这个注释只是写给看不懂的人的;
而且这段代码的完成时间是8月11日;
我8月1日入的基础班;当时并没学到集合,
这段代码只是写给还没有学到集合或希望拓展思维的人看的;

评分

参与人数 1黑马币 +3 收起 理由
水月灬清影 + 3 嗯,我也有点较真儿了,还是鼓励一下你!.

查看全部评分

回复 使用道具 举报
这种方法只会锻炼你的思维能力,还有对数组的理解能力。很不错的
回复 使用道具 举报
obvilion 发表于 2016-9-2 19:05
这种方法没你说的那么不堪,比用集合只多了一道n次的遍历除重,用集合的contains方法也是从第一个比到最后 ...

呵,这就有意思了,怎么我用了新特性就叫失去创新的动力了?这到底是跟紧创新脚步还是因循守旧?
首先,是你说的
“其底层的算法还是要做判断为了达到除重效果就必须使用Set
为了保证顺序不变,只能使用LinkedHashSet;”  
  我才用的 list 和 contains()  ;
其次,你要是问集合优势在哪里?就“简洁明了”一个词。什么Integer不合适,什么自动拆装箱花的时间耗得资源,就清清白白几行不用注释的代码,跟你那大段注释,同样效果的代码放在一起,还用说别的?你要非心疼计算机,不心疼你自己,别用呗,算盘打咯。
再次,你说我要转成新数组费劲,你能在原数组上改?不一样要新建数组储存?
最后,我之前说了,你随意,你觉得你的实用你的创新你就用,不爱用集合你就不用,我说我的想法,少上纲上线。
回复 使用道具 举报
水月灬清影 发表于 2016-9-2 11:33
我的天,时间复杂度都扯出来了……
[Java] 纯文本查看 复制代码
ArrayList array = new ArrayList();
		//遍历原 ...[/quote]

这种方法没你说的那么不堪,比用集合只多了一道n次的遍历除重,用集合的contains方法也是从第一个比到最后一个,我前半段的工作和集合底层的做的工作没什么区别,而且用集合,可以更简单
[mw_shl_code=applescript,true]
		LinkedHashSet<Integer> lhs = new LinkedHashSet<> ();
		for (int i : num) {
			lhs.add(i);
		}
		Integer[] newNum = lhs.toArray(new Integer[0]);

如果用Integer[]接收我只要三行就够了,
大括号可以去掉;但是关键是要用int类型的数组来接收数据,你这里用Integer[]显然是不合适的而且自动拆装箱
也是要调用资源的,的确这些步骤不需要你去考虑,但是执行这些额外步骤一样需要时间,再加一步转化为int[]数组,请问集合的优势在哪里?我们不能因为工具好用,就失去了创新的动力
回复 使用道具 举报
确实有点麻烦了  目前阶段转成集合来操作同样能满足需求的
回复 使用道具 举报
本帖最后由 水月灬清影 于 2016-9-2 11:37 编辑

我的天,时间复杂度都扯出来了……
[Java] 纯文本查看 复制代码
ArrayList<Integer> array = new ArrayList<Integer>();
		//遍历原数组,如果不重复就添加到集合
		for(Integer i:num){
			if(!array.contains(i)){
				array.add(i);
			}
		}
		Integer[] newNum = new Integer[array.size()];
		array.toArray(newNum);


我list可以保证有序,contains()可以保证不重复,代码简单,底层也是数组。你要说数据量增大,重复元素减少,集合速度不能保证,那你的代码是循环嵌套查重,样本越大,你查的速度越慢,我从头到尾遍历一次就可以,你得遍历多少次?我就不拿100万个数测了…………你随意,不爱用集合就不用,我就说说我的想法。


回复 使用道具 举报
水月灬清影 发表于 2016-9-2 09:58
我宁可用集合中转………………

用集合中转无非就是代码简单点了,
效率还是一样的算法时间复杂度一样是o(n^2);
其底层的算法还是要做判断为了达到除重效果就必须使用Set
为了保证顺序不变,只能使用LinkedHashSet;
这玩意底层也是数组实现的;在重复元素过多的情况下用集合是会快一些,
但是当数据量增大,重复元素变少,用集合的速度就不一定能保证了
而且我们讲这题时,是没有学集合的.
回复 使用道具 举报
我宁可用集合中转………………
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马