package com.mianshi.test;
import java.util.ArrayList;
import java.util.List;
//需求:给出两个已经排序的数组,求两个数组的交集
//思路:取两个数组的交集,最直接的办法就是建两个for循环,遍历两个数组一个一个进行对照,若等就记录下来。但是这种办法效率比较低,给出的数组
//已经是排好序的所以我们可以使用二分查找,这样效率就会大大提高。还有一个地方,因为事先不知道有多少交集,即新数组的长度不确定,所以我们要
//借助List<Integer>集合。先把交集存在list中,之后再存入数组。如果数组比较大,我们最好遍历小的数组,二分查找大的数组,这样效率也会提高。
//具体代码如下
public class Jiao_Ji_One {
public static void main(String[] args) {
int[] a = {1,3,5,7,9};
int[] b = {2,3,4,5,6,7};
int[] c = jiaoJi(a, b);
for (int i=0; i<c.length; i++) {
System.out.print(c[i] + " ");
}
}
public static int[] jiaoJi(int[] a, int[] b) {
List<Integer> list = new ArrayList<Integer>();
if (a.length < b.length) {
for (int i=0; i<a.length; i++) {
int k = efcz(b, a[i]);
if (k != -999999999) {
list.add(a[i]);
}
}
} else {
for (int i=0; i<b.length; i++) {
int k = efcz(a, b[i]);
if (k != -999999999) {
list.add(b[i]);
}
}
}
int[] c = new int[list.size()];
for (int i=0; i<list.size(); i++) {
c[i] = list.get(i);
}
return c;
}
//二分查找 -999999999是自己定义的,可以根据自己的实际需要定义
public static int efcz(int[] arr, int a) {
if (arr == null) {
return -999999999;
}
int start = 0;
int model = arr.length/2;
int end = arr.length - 1;
while(start <= end) {
int value = arr[model];
if (a > value) {
start = model+1;
} else if (a < value) {
end = model-1;
} else {
return model;
}
model = (start+end)/2;
}
return -999999999;
}
}
输出结果:
3 5 7
更多问题请访问
http://www.exceptionhelp.com/posts/530
分享到:
相关推荐
例如,如果要查找以下三个数组的交集(公共元素) a = [ 1 3 4 6 8 9 ]; b = [ 3 1 0 8 6 4 ]; c = [ 7 8 1 9 3 4 ];, 您需要首先将它们全部放入一个单元格数组中,即单元格 = {a, b, c}; 然后你可以使用“cell”...
leetcode双人赛 Golang multi-solutions for leetcode 每道题目均有最优算法。 AC ...两个数组的交集 两个数组的交集 II 翻转对 数组的相对排序 剑指 Offer 40. 最小的k个数 面试题 08.03. 魔术索引
两个数组的交集 II -[x] 简单:66. 加一 -[x] 简单:283. 移动零 -[x] 简单:88.合并两个有序数组 -[x] 简单:268. 丢失的数字 -[x] 简单:724. 寻找数组的中心索引 -[x] 简单:35. 搜索插入位置 -[x] 简单:228. ...
(349)两个数组的交集 (442)查找数组中的所有重复项 (605)可以放花 (624)数组中的最大距离 (723)糖果粉碎 (896)单调数组 (933)最近通话次数 (941)有效的山阵 (977)排序数组的平方 (1103)向人们...
两个数组的交集 (442) 查找数组中的所有重复项 (605) 可以放置鲜花 (624) 数组中的最大距离 (723) 糖果粉碎 (896) 单调阵列 (933) 最近通话次数 (941) 有效的山阵 (977) 有序数组的平方 (1103) 分发糖果给人们 二分...
6.数据结构中评价算法的两个重要指标是(时间复杂度和空间复杂度) 【北京理工大学 2001 七、1(2分)】 7. 数据结构是研讨数据的_(1)物理结构_和_(2)逻辑结构 _,以及它们之间的相互关系,并对与这种结构定义...
两个链表的交集 0148 排序表 AY 0162 寻找峰值元素 0179 最大数 星期日 0131 回文分区 0108 将有序数组转换为二叉搜索树 第 9 周问题列表: 杰森 0277 找名人 0136 单号 GG 0101 对称树 0329 矩阵中最长的递增路径 ...
CompareFileTime 对比两个文件的时间 CopyFile 复制文件 CreateDirectory 创建一个新目录 CreateFile 打开和创建文件、管道、邮槽、通信服务、设备以及控制台 CreateFileMapping 创建一个新的文件映射对象 ...
3.2 寻找上一个星期五 112 3.3 计算日期之间的时段 114 3.4 计算歌曲的总播放时间 115 3.5 计算日期之间的工作日 116 3.6 自动查询节日 118 3.7 日期的模糊查询 121 3.8 检查夏令时是否正在实行 123 3.9 时区...
8.求两个数组中的相同元素 141 9.查找一个中间大的数… 141 10.编写类 String的构造析构赋值函数…,…,…,,, 141 11.输入两个宇符串,输出第二个字符串在第一个字符串中的位序 143 12.方块寻径…… …144 ...