精华内容
下载资源
问答
  • jsreduce函数的妙用 <script> // 值集数组 let arr1 = [1,2] let arr2 = [2,3] let newArr1 = arr1.filter(val=>... return new Set(arr2).has(val) ... // 对象数组取某个对象元素相同的交集 let arr..

     js reduce函数的妙用

    <script>
          // 值集数组
          let arr1 = [1,2]
          let arr2 = [2,3]
          let newArr1 = arr1.filter(val=>{
            return new Set(arr2).has(val)
          })
          console.log(newArr1) // [2]
    
          // 对象数组取某个对象元素相同的交集
          let arr3 = [{a:'1',b:'12'}, {a:'0', b:'12'}]
          let arr4 = [{a:'2',b:'23'}, {a:'0', b:'12'}]
          let arr5 = arr3.map(item=>item.a)
          let newArr2 = arr4.filter(info=>{
            return new Set(arr5).has(info.a)
          })
          console.log(newArr2) // [{a:'0', b:'12'}]
          
          // 多个数组取交集-reduce()方法对数组中的每个元素执行一个由自己提供的函数,将其结果汇总为单个返回值
          let arr6 = [1,2,3]
          let arr7 = [3,4,5]
          let arr8 = [{a:'2',b:'23'}, {a:'0', b:'12'}, {a:'3', b:'34'}]
          
          // 定义一个取交集的函数
          function intersection(getar1, geta2, key) {
            let arr = getar1.map(item=>item[key])
            let newArr3 = geta2.filter(info=>{
              return new Set(arr).has(info[key])
            })
            return newArr3
          }
    
          let getAllObjArr = [arr3,arr4,arr8]  // reduce()方法处理处理数组元素,现将所有的数组合并在一个数组中
          let getNewArr = getAllObjArr.reduce((a, b)=>{ 
            return intersection(a, b, 'a')
          })
          console.log(getNewArr) // [{a:'0', b:'12'}]
    
           
          // reduce函数方法
          // reducer 函数的返回值分配给累计器,该返回值在数组的每个迭代中被记住,并最后成为最终的单个结果值。
          // MDN上的栗子
          const array1 = [1, 2, 3, 4];
          const reducer = (accumulator, currentValue) => accumulator + currentValue;
    
          // 1 + 2 + 3 + 4
          console.log(array1.reduce(reducer));
          // 5 + 1 + 2 + 3 + 4
          console.log(array1.reduce(reducer, 5));
    
          // reducer 函数接收4个参数:
    
          // Accumulator (acc) (累计器)
          // Current Value (cur) (当前值)
          // Current Index (idx) (当前索引)
          // Source Array (src) (源数组)
        </script>

     

    展开全文
  • 如题,多个数组取交集(共同拥有元素),思路取第一个数组去跟每个数组中的元素对比,同时比较数据类型有救返回没有就返回null。 下面介绍到的算法数据格式是二维数组如: const parentArray = [[11,12,343,34...

    如题,多个数组中取交集(共同拥有元素),思路取第一个数组去跟每个数组中的元素对比,同时比较数据类型有救返回没有就返回null。

    下面介绍到的算法数据格式是二维数组如:

    const parentArray = [[11,12,343,34,432,34,4],[54,3,4,5,2,52],[34,2,3,23,423,234]]

    算法明细:

    var arr = arrs.shift(); 
      for(var i=arrs.length;i--;){
         var p = {"boolean":{}, "number":{}, "string":{}}, obj = [];
         arr = arr.concat(arrs[i]).filter(function (x) {
           var t = typeof x;
           return !((t in p) ? !p[t][x] && (p[t][x] = 1) : obj.indexOf(x) < 0 && obj.push(x));
         });
         if(!arr.length) return null; 
      }
      return arr;

     

    转载于:https://www.cnblogs.com/leungUwah/p/9236590.html

    展开全文
  • 思路:把所有数组合并成一个数组,然后再遍历找到重复的 元素 var a = [1,2,3,4,9]; var b = [8,0,2,3,4]; var c = [1,3,4]; var num = 3; function mergeArr(num, ...arr){ let tmpA = arr....

    思路:把所有数组合并成一个数组,然后再遍历找到重复的 元素

    var a = [1,2,3,4,9];
    var b = [8,0,2,3,4];
    var c = [1,3,4];
    var num = 3;
    
    function mergeArr(num, ...arr){
        let tmpA = arr.reduce((lastArr, item)=>{
            lastArr = lastArr.concat(item);
            return lastArr;
        },[])
        console.log(tmpA)
        return qujiao(tmpA,num);
    }
    
    function qujiao(arrs, num) { 
        let jiao = [];
        let obj = arrs.reduce((last, item) =>{
            if(!last[item]){
                last[item] = 1;
            }else{
                last[item] = last[item] + 1;
            }
            return last;
        },{})
        
        for(key in obj){
            if(obj[key] == num){
                jiao.push(key);
            }
        }
        return jiao;
    }
    mergeArr(num,a,b,c);

     

    展开全文
  • 原创:搜索算法之两个数组取交集的算法 在垂直搜索中,有很方法可以控制返回结果的数量。比如用户输入"上海世博会",要求只显示跟上海世博会相关的内容。有三种方法可以参考:①...

    原创:搜索算法之两个数组取交集的算法

    在垂直搜索中,有很多方法可以控制返回结果的数量。比如用户输入"上海世博会",要求只显示跟上海世博会相关的内容。有三种方法可以参考:①BooleanQuery,AND逻辑②phraseQuery,精读最高,只出现"上海世博会"连续的短语的文档③solr的模糊匹配查询。如果采用第一种方案,在垂直搜索中(比如Lucene),如果用户的查询向量(经由queryParser处理,调用中文分词,并且形成查询语法树)Term t = {xx,xx,……},BooleanQuery为AND时,向量中每一个维度的元素得到对应的倒排列表,倒排列表由许多的倒排索引项构成,然后取其中有交集的文档编号,然后进行排序。其核心思想类似于如下问题:

    现有两个数组:int []data1 = {12,45,65,2,5} int []data2 = {12,5,-8,9},取其中的交集。

    关于这个算法,最主要的精力是放在如何降低时间复杂度上。采取先排序再找交集的算法或者以空间换时间的算法,都不可取,要么时间复杂度高,要么就是空间复杂度高。Lucene源代码里,采用的是先排序,然后定义两个指针开始搜索相同的数字。当容量非常大时,这个算法的性能其实是不太好的。如果采用quickSort,最坏的复杂度是n^2,平均复杂度是nlgn。如果容量超过1千万,mergeSort会好一点,最坏复杂度为nlgn。大量的时间将浪费在排序上。换个思路,对于数字的处理,既然取交集,不妨从整体着手,避免一开始就陷入局部讨论。急于算法的实施,效果反而不好。对于不同的问题,要善于从整体考虑,分析内部的规律。那就要学会观察,类比和迁移,学会演绎推理。对于一个问题的解决,可以从一个类似的比较简单的事物入手,找出规律,然后进行迁移,改进,做近一部的研究。很多程序员都会各种排序算法,比如mergeSort,quickSort,HeapSort and son on。一开始进行排序,可能是程序员的惯性思维。对于这个算法,如果你的第一想法是它的话,说明你在算法上,还有提升空间,思维方式需要改变。解决一个问题,最忌讳的就是思维定势。经验有好处也有坏处。正确的做法是,忘记储备的知识,采用最原始的手段,从研究表象入手,寻找内部的规律,然后用理论验证。其次,进行迁移,演化。单独从排序算法来看的话,如果数据量<1000w的话,quickSort性能会好一些,达到上亿级别的,mergeSort会好一些。如果给你一个海量数据,要求寻找出topK最大值或者最小值来,采用排序当然能解决。因为抛开问题本身,单独来看,mergeSort可能是最好的。但是,对于这个问题,性能却是十分拙劣的。所以说,没有绝对好的算法。抛开应用场景的算法,即使是好的,最后也可能是拙劣的。这个问题的着手点,可以从下面开始:

    对于数字取交集,可以画一个数轴,先从简单的连续型数字入手,然后再迁移到离散型的数字。看下图:

    对于图中的①,A~B,C~D为两个数组的取值范围,交集就是CB部分。如果两个数组中的数字是连续型的,那么,CB就是结果,非常简单。但是,大部分数组是离散型的数字。CB里面的数字,只有一部分是想要的结果。需要对CB进行进一步的处理。很容易想到的是,把AC和BD部分砍掉,对剩余的CB部分进行相同的处理,如图中的②和③。在这个过程中,每次找相同的数字,都是从只有两个数字(取值范围)的集合中寻找,之后两个数组只保留取值范围的交集部分,然后不断循环,大大降低了时间和空间复杂度这个算法本身并不难,但是,如何从两个取值范围的数组里寻找相同的值,(从AB和CD里找),如何判断算法何时收敛,需要耐心地寻找规律,逻辑分类要清晰,经得起各种等价值和边界值的测试,保证算法准确无误,可能要花费一些时间。整理起来,思路大致如下:

    即:1.分别计算两个数组的min和max(取值范围),加入到rangeList 中,然后计算rangeLis中重复的数值,加入到result(list)中;

    2.计算rangeList的取值范围交集,比如[1,20,3,15],两个数组的取值范围交集为[3,15],放在数组中,然后根据这个交集分别去除两个数组中不在此范围内的数值,清空rangeList,清零数组;

    3.重复上述步骤,直到符合终止条件位置。

    从取值范围中寻找相同值以及算法收敛条件:

    寻找相同值的过程中,要注意收敛条件的判断,所以比较好的思路是:把两个取值范围加到一个集合中,再把这四个数字加到set中,分别求和,然后根据set的size大小辅助判断。和值sum1和sum2分别为第一个集合和set的和值。①size == 1:把结果加载到结果集中,算法收敛;

    ②size == 3:说明有一对数字重复。重复的数字分布情况有两种:一是分别分布在两个数组中;二是全部分布在一个数组中,这种情况,直接返回结果,算法收敛;对于第一种情况,sum1 - sum2就是相同的数值,加载到结果集中,继续后面的处理。

    ③size == 2:说明有两组数字重复,分布情况如第一张图的下面部分,2代表矩阵两行相等,0代表矩阵两列相等,1代表一行一列各相等。如果是2的话,直接返回结果,算法收敛;如果是0的话,set本身就是相同的数值。

    ④size == 4:有两种情况,其中一种是两个压缩集合没有交集,在后面的代码中应该增加收敛判断条件,如果有交集,直接进行后面的处理。

    在这个迭代过程中,循环终止的整体条件是:两个数组中有任何一个size == 0或者取值范围的交集倒置。

    通过不断减少数组的元素个数,动态控制迭代次数,迭代次数大大降低,当容量非常大时,会显示出优越的性能。此为目前最优的算法。

    以上是逻辑实现,最重要的还是数据结构,由于在这个过程中,会不断地去除数组中的数值,所以底层采用链式存储的线性表,性能会比较高。

    经过调试后,准确无误,现在上传代码,以供分享:

    package com.txq.test;
    
    import java.util.List;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Queue;
    import java.util.Set;
    import java.util.concurrent.ConcurrentLinkedDeque;
    /**
     * 两个数组取交集算法,优于先排序后搜索的算法
     * @author XueQiang Tong
     * @date 2017/10/21
     */
    public class IntersectionForPairArray {
    	private List<Integer> inter = new ArrayList<Integer>(4);//存储压缩后的集合	
    	private Set<Integer> s = new HashSet<Integer>(4);//过滤压缩集合中的重复数字
    	private Queue<Integer> arr1 = new ConcurrentLinkedDeque<Integer>();//存储原始数据的队列,链式存储
    	private Queue<Integer> arr2 = new ConcurrentLinkedDeque<Integer>();
    	private List<Integer> result = new ArrayList<Integer>();//结果集
    	private List<Integer> intersec = new ArrayList<Integer>(2);//压缩集合的交集
    	
    	public List<Integer> intersection(int[]ar1,int[]ar2){
    		if(ar1.length == 0 || ar2.length == 0 || ar1 == null || ar2 == null) return result;
    		
    		//1.把数据加载到队列中
    		int len = Math.max(ar1.length, ar2.length);
    		for (int i = 0;i < len;i++){
    			if (i <= ar1.length-1){
    				arr1.add(ar1[i]);
    			}
    			if (i <= ar2.length-1){
    				arr2.add(ar2[i]);
    			}			
    		}
    		while(true) {
    			//2.集合压缩
    			inter.add(Collections.min(arr1));
    			inter.add(Collections.max(arr1));
    			inter.add(Collections.min(arr2));
    			inter.add(Collections.max(arr2));
    			
    			for (int i = 0;i < inter.size();i++){//把压缩后的集合加入到set中
    				s.add(inter.get(i));				
    			}
    			int size = s.size();
    			//下面开始寻找相同的数字
    			
    			if(size == 4){				
    				
    			}
    			//先求和	
    			int sum = computeSum(inter);		
    			int sum1 = computeSum(s);
    			int res = sum - sum1;
    			
    			if (size == 3){				
    				if ((inter.get(0) == inter.get(1)) || (inter.get(2) == inter.get(3))){
    					return result;					
    				}
    				else {					
    					result.add(res);
    					arr1.remove(res);
    					arr2.remove(res);
    				}
    			}
    			if (size == 2) {//有三个元素和两对儿元素重复的情况,收敛情况是两个压缩集合各自重复,三个元素重复的情况其结果是res/2
    				if ((inter.get(0) == inter.get(1)) && (inter.get(2) == inter.get(3))) {
    					return result;					
    				}				
    				else {
    					if((inter.get(0) == inter.get(2)) && (inter.get(1) == inter.get(3))){
    						result.addAll(s);
    						for (int element:s){
    							arr1.remove(element);
    							arr2.remove(element);
    						}						
    					} else {
    						result.add(res/2);
    						arr1.remove(res/2);
    						arr2.remove(res/2);
    					}
    					
    				}
    			}
    			if (size == 1) {
    				result.addAll(s);
    				return result;
    			}
    			//4.计算inter的交集,并分别去除两个集合中不在此范围内的元素			
    			intersec.add(Math.max(inter.get(0),inter.get(2)));
    			intersec.add(Math.min(inter.get(1),inter.get(3)));
    			
    			if (intersec.get(0) > intersec.get(1)) break;//当size == 4并且两个压缩集合没有交集时,到此终止
    			
    			removeElement(arr1);
    			removeElement(arr2);
    			
    			if (arr1.size() == 0 || arr2.size() == 0) break;
    			
    			s.clear();
    			inter.clear();
    			intersec.clear();
    		}
    		return result;	
    		
    	}
    
    	private void removeElement(Queue<Integer> queue) {
    		Iterator<Integer> it = queue.iterator();
    		while (it.hasNext()){
    			int n = it.next();
    			if (n < intersec.get(0) || n > intersec.get(1)) {
    				queue.remove(n);
    			}
    		}
    	}
    
    	private int computeSum(Collection<Integer> col) {
    		int sum = 0;
    		for (int i :col){
    			sum += i;			
    		}
    		return sum;		
    	}	
    	
    }
    

     数据结构,底层就两种,一为顺序存储的散列结构,另一个为链式结构struct。第一种结构,在搜索方面有优势,另一个在存储空间及增删改方面有优势。利用这两种数据结构,结合数据安全(比如CAS算法,多线程)和算法,可以根据业务需求设计出更加复杂的数据结构,比如三叉树,哈夫曼树,红黑树,堆 and so on。平时使用现成的库里的数据结构,比如map,set等等,底层都是基于上述两种结构。不同的结构,有不同的优势。比如,solr内部自置的搜索智能提示功能,数据结构采用三叉树。三叉树的优势是树中有树,能够节省内存空间,但是在查找方面,不及平衡的二叉树。所以,在构建三叉树的时候,采用了折中处理,以提高搜索时间。设计平衡的二叉树,就是要解决时间和空间问题,所以底层数据结构,才采用struct(封装对象属性和指针的类)。

    posted @ 2016-05-12 19:44 佟学强 阅读(...) 评论(...) 编辑 收藏
    展开全文
  • //数据结构如下,是一个二维数组,需要获取到每个数组里的交集 let arr = [ [1,2,3,4],[3,4,6],[4,5] ] 第一步:设置一个变量,minArr,表示所有数据里最小长度的数组,后面通过这个最小长度数组的数据和其他的...
  • 1.两个数组交集I最近在刷二分的题,找到这一题,做个总结,二分的复杂度并不低,不是最优解方法1:Set(题解中出现最多的)publicint[]intersection(int[]nums1,int[]nums2){if(nums1==null||nums1.length==0||nums2...
  • 在垂直搜索中,有很方法可以控制返回结果的数量。比如用户输入"上海世博会",要求只显示跟上海世博会相关的内容。有三种方法可以参考:①BooleanQuery,AND逻辑②phraseQuery,精读最高,只出现"...
  • 有序数组交集

    2014-12-14 00:50:00
    设两个指向两个数组末尾的指针,较小的那个数在另一个数组中二分查找,找到,则存在一个交集,并且将该目标数组的指针指向该位置前一个位置。如果没有找到,同样可以找到一个位置,使得目标数组中在该位置后的数...
  • 一维数组取交集是非常的简单,直接用一个函数即可。array_intersect($arr, $ar),那么二维数组又是如何的取出它们的交集呢,可能有人同样想用这个函数,但结果却不是我们想要的。下面有这样的一个数组:$arr=array...
  • 1. 对于两个或者多个(个数确定)数组取交并集非常简单,通过内置函数 2. 二维数组取交并集,我们可以循环法: 3. 但是如果一个需求是,通过勾选多少组数据,然后对这N组数据进行取交集,你该怎么办? 这时候你不...
  • 最劲项目需要用到js数组去重和交集的一些运算,我的数组元素数可能到达1000以上,网上的实现方式都是2次循环,性能不适合我的需求,1000*1000那次数太了,所以我这里采用对象object来做处理,用空间换时间,code...
  • 多个二维数组如何取出它们的交集

    千次阅读 2014-10-29 10:30:13
    一维数组取交集是非常的简单,直接用一个函数即可。array_intersect($arr, $ar),那么二维数组又是如何的取出它们的交集呢,可能有人同样想用这个函数,但结果却不是我们想要的。下面有这样的一个数组:  $arr=...
  • 不过由于手机的参数,且不同的手机其参数差异大,所以参数表结构通常是纵表(一参数是一行),而不是横表(一参数是一列),此时使用若干参数来取结果,通常就是把每单独参数来取结果,再一起取交集。...
  • stream 流 实现 集合 取交集

    千次阅读 2020-05-05 23:48:49
    提供多个数组,取出所有数组的 交集 示例: 输入: [1,2,3,4,5,6] [2,3,1,5,34] [2,45,6] ... [2,...] 输出: [2] 思路: 获取流 对流进行取交集操作 将结果转成新的集合输出 源码: 具体逻辑代码 private ...
  • 取交集阶段

    2018-11-15 14:24:16
    多个List求交集 如以下数组,List&lt;1,4,2,8&gt; l1 List&lt;8,4,3,2&gt; l2 List&lt;17,2,3,4&gt; l3 其交集为List&lt;2,4&gt;   @Test public void test(){ List&lt;...
  • PHP数组操作大全

    2018-11-23 17:33:42
    1、取多个一维数组的交集(两个数组为例): $a = ['阿哲','浅蓝','老李','大衣','大嘴','文儿']; $b = ['阿佑','大嘴','于一','刘一手','王小源','王冕']; $result = array_intersect($a,$b); var_dump($...
  • php对数组操作的函数

    2019-09-26 12:34:14
    array_reverse 以相反的顺序返回数组 ...array_intersect两个或多个数组取交集 implode和explode也只对一维数组有效 转载于:https://www.cnblogs.com/jcydd/p/7299624.ht...
  • JSON字符串和java对象的互转【json-lib】在开发过程中,经常需要和别的系统交换数据,数据交换的格式有XML、JSON等,JSON作为一轻量级的数据格式比xml效率要高,XML需要很的标签,这无疑占据了网络流量,JSON在...
  • 最劲项目需要用到js数组去重和交集的一些运算,我的数组元素数可能到达1000以上,网上的实现方式都是2次循环,性能不适合我的需求,1000*1000那循环次数太了,所以我这里采用对象object来做处理,用空间换时间,...
  • 三个函数,都是求两个或两个以上数组的交集。区别在于是键上的交集,还是值上的交集。 拼写 interset 相交,交叉 ...如果是三个或三个以上的数组,就是求这多个数组中都存在的 array_intersect 检测的是数组中的...
  • js常用方法

    2020-05-20 16:04:44
    多个数组交集 arrayintersection(arrs){//二维数组交集 let arr = arrs.shift() //第一数组跟每一个对比筛选 arrs.forEach(t => { arr = arr.filter((num) => { return t.indexOf(num) !== -1 }) }) ...
  • 九宫格数独游戏解法(一)

    千次阅读 2013-07-27 23:45:50
    这个简单程序最复杂的地方是要把直观上的三种情况得出三个独立的值,然后取交集,尤其是在同一个循环里边实现第三个数组,想了我很久。 // NO.game.cpp : 定义控制台应用程序的入口点。 // #include #include...
  • 现在给你一长度为n的数组a,让你构造一新的数组b使得b和a位置相同且数相同的位置有x,数的multiset集合的交集大小为y。 题解: 那么首先由于数量的数对于y-x的限制比较大,那么我们就优先将数量最多的数...
  • 6.2.18 SkipWhile 条件第一次不成立就失效,将后面的数据全 20 6.2.19 Cast 将集合转换为强类型集合 21 6.2.20 OfType 过滤集合中的指定类型 21 6.3 不延迟(浅复本) 21 6.3.1 Single 集合中符合条件的唯一元素...

空空如也

空空如也

1 2
收藏数 34
精华内容 13
关键字:

多个数组取交集