有序数组中与任意数组查找不同的部分-二分查找

题目:在一串有序数组中,给出一串随机数组查找其中不同的部分

数组A:{2,3,5,8,9,11}

数组B:{9,8,2,10,1}

结果:10,1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

public class GetAllNotIncluded {

	// 利用二分查找查找与子串不同的部分
	public static List<Integer> getAllNotIncluded(int A[], int B[]) {
		List<Integer> res = new ArrayList<>();
		for (int i = 0; i < B.length; i++) {
			int L = 0;
			int R = A.length - 1;
			boolean flag = false;
			while (L <= R) {
				int mid = L + ((R - L) >> 1);
				if (A[mid] == B[i]) {
					flag = true;
					break;
				}
				if (A[mid] > B[i]) {
					R = mid - 1;
				} else {
					L = mid + 1;
				}
			}
			if (!flag) {
				res.add(B[i]);
			}

		}

		return res;

	}
	//比较函数
	public static List<Integer> comparator(int A[],int B[]){
		List<Integer> res =new ArrayList<>();
		for(int i=0;i<B.length;i++) {
			boolean flag=false;
			for(int j=0;j<A.length;j++) {
				if(A[j]==B[i]) {
					flag=true;
					break;
				}
			}
			if(!flag) {
				res.add(B[i]);
			}
		}
		return res;
	}
	
	//获取随机数组
	public static int[] getRandomArray(int maxSize,int maxValue) {
		int[] arr=new int[(int)((maxSize+1)*Math.random())];
		for(int i=0;i<arr.length;i++) {
			//获取 -maxVlaue + 1 ~ maxValue 的值
			arr[i]=(int)((maxValue+1)*Math.random())-(int)(maxValue*Math.random());
		}
		
		
		return arr;
		
	}
	public static boolean isEqual(List<Integer> list1,List<Integer> list2) {
       if(list1.size()!=list2.size()) {
	return false;
}
	HashMap<Integer,Integer> map=new HashMap<>();
	for(Integer i : list1) {
		//如果没有A集合中的这个元素,则添加进集合
		if(!map.containsKey(i)) {
			map.put(i, 0);
		}
		//如果存在即更新对应value值
		map.put(i,map.get(i)+1);
	}
	for(Integer i:list2) {
		//如果不存在,则直接return false
		if(!map.containsKey(i)) {
			return false;
		}
		//如果重复存在的值 数量不同
		map.put(i,map.get(i)-1);
		
		if(map.get(i)<0) {//即第二个集合数量重复值多于第一个集合
			return false;
		}
	}
	return true;
}
	public static void main(String[] args) {
		int tests =50000;
		//有序的数组最大长度
		int sortedArrayMaxSize = 300;
		//未排序的数组最大长度
		int unsortedArrayMaxSize = 10;
		//变量范围
		int maxValue = 100;
		boolean flag = true;
		for (int i = 0; i < tests; i++) {
			int[] A = getRandomArray(sortedArrayMaxSize, maxValue);
			int[] B = getRandomArray(unsortedArrayMaxSize, maxValue);
			//二分查找-有序数组
			Arrays.sort(A);
			List<Integer> res1 = getAllNotIncluded(A, B);
			List<Integer> res2 = comparator(A, B);
			if (!isEqual(res1, res2)) {
				flag = false;
				break;
			}
		}
		System.out.println(flag ? "Nice!" : "Fucking fucked!");
		//例
		int A[]= {8,5,6,8,2,8,2,3,5,4,5,6,7,9,9,3,2,11,2,21,26};
		int B[]= {1,2,2,3,4,10};
		Arrays.sort(A);
		List<Integer> res1 = getAllNotIncluded(A, B);
		List<Integer> res2 = comparator(A, B);
		Iterator it1=res1.iterator();
		Iterator it2=res1.iterator();
		while(it1.hasNext()) {
			System.out.print(it1.next()+" ");
		}
		System.out.println();
		while(it2.hasNext()) {
			System.out.print(it2.next()+" ");
		}

	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

JAVA集合类汇总

数组(可以存储基本数据类型)是用来存现对象的一种容器,但是数组的长度固定,不适合在对象数量未知的情况下使用。 集合(只能存储对象,对象类型可以不一样)的长度可变...

1683
来自专栏desperate633

Top 6 常见问题关于Java中的Map1 将Map转换成一个List2 遍历map中的键值对3 根据Map的key值排序4 根据Map的value值排序5 初始化一个静态的不可变的Map6 Has

我们都知道Map是一种键-值对的数据结构,每个键都是唯一的!本文讨论了关于Java中Map使用的最常见的8个问题。为了叙述的简单,所有的例子都会使用泛型。并且本...

813
来自专栏Java技术分享圈

Java集合之map 集合使用

832
来自专栏Java爬坑系列

【Java入门提高篇】Day20 Java集合类详解(三)List接口

  今天要说的是Collection族长下的三名大将之一,List,Set,Queue中的List,它们都继承自Collection接口,所以Collectio...

2457
来自专栏cs

java的几个不错习题

现在定义如下的一个数组:intoldArr[]={1,3,4,5,0,0,6,6,0,5,4,7,6,7,0,5},要求将以上数组中值为0的去掉,将不为0的值存...

842
来自专栏浪淘沙

java学习day07 常用API

2018.6.11 1.object 所有类的父类 toString 打印对象的地址值 hashCode 对象的存储位置的算法 ...

1423
来自专栏吾爱乐享

java学习之二分查找法代码

1382
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题16反转单链表

本题的详细解析均在代码中注释: /** * 题目:将单链表反转,并输出反转后链表的头结点 * @author 大闲人柴毛毛 */ public class...

41911
来自专栏Java帮帮-微信公众号-技术文章全总结

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&正则【悟空教程】

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&简单正则表达式【悟空教程】

1062
来自专栏黑泽君的专栏

java基础学习_集合类04_Map接口、Collections工具类_day18总结

============================================================================= ==...

861

扫码关注云+社区

领取腾讯云代金券