算法练习 - 判断是否存在相交数组

骑猪看日落 2023-03-02 13:21 26阅读 0赞

### 题目 ###

> 判断数据内，元素是否有交集. 数组内的值都是连续值.  
> 例如：\[\[1,6\], \[5,9\],\[16,30\],\[8,10\]\]  
> 输入: 一个二维数组.  
> 返回: 布尔类型数据 true or false.

--------------------

### 解题思路 ###

*  思路1: 两两比较.

两两比较主要包括4种情况.

Case1: 不相交  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70]

if(A.尾巴>B.头){
    	resultFlag = false;
    }

Case2: 不相交

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 1]

if(B.尾巴>A.头){
    	resultFlag = false;
    }

Case3: 左交

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 2]

if(A.头<=B.头&&A.尾>=B.头){
    	resultFlag = true;
    }

case4: 右交  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 3]

if(B.头<=A.头&&B.尾>=A.头){
    	resultFlag = true;
    }

由上面的4图可以知道. 我们需要知道的相交情况. 主要就是2种. `左交`和`右交`.  
`左交`和`右交`其实还可以做一个判断. 将`A.头`和`B.头`先进行比较, 选择头节点小的作为先比较节点.(`一个简单优化, 可以设置也可以不设置.`)

*  思路1: 简单的编码如下所示

public static boolean insetOrNotBetweenTwoArrayMethod1(int []arrayA,int arrayB[]) {
    		// 返回值结果
    		boolean flag = false;
    		if(arrayA.length>0&& arrayB.length>0) {
    			int beginA = arrayA[0];
    			int endA = arrayA[arrayA.length-1];
    			int beginB = arrayB[0];
    			int endB = arrayB[arrayB.length-1];
    			// 左交
    			if(beginA<=beginB&&endA>=beginB) {
    				flag = true;
    			}
    			// 右交
    			else if(beginB<=beginA&&endB>=beginA) {
    				flag = true;
    			}
    			// 其余2种情况都是不相交的 可以不用写
    			else if(endA >=beginB || endB>=beginA) {
    				flag = false;
    			}
    		}
    		return flag;
    	}
    	// 思路1 左交 右交
    	public static boolean insetOrNotInArraysMethod1(int array[][]) {
    		boolean flag = false;
    		int arrayCount = array.length;
    		for(int i=0;i<arrayCount;i++) {
    			for(int j=i+1;j<arrayCount;j++) {
    				// 两两比较
    				flag = flag & insetOrNotBetweenTwoArrayMethod1(array[i],array[j]);
    				if(flag) {break;}
    			}
    			if(flag) {break;}
    		}
    		return flag;
    	}

优点： 利用规律一目了然.  
缺点: 需要两两比较.

--------------------

*  思路2: 排序后比较.

思路1介绍了两两进行比较. 两两比较的复杂度为`O(N^2)`. 思路2为先将2者按照头节点排序, 随后进行比较.

比如例子:

例如：[[1,6], [5,9],[16,30],[8,10]]
    排序后: [[1,6], [5,9],[8,10],[16,30]]

排序之后, 比较第二个节点的值头是否在第一个之内即可. 也就是我们说的左交情况.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 2]

步骤1: 排序.
    步骤2: for(1...N) 比较是否存在左交情况.

这边有一个特别的情况, 那就是相等. 对于相等来说, 比如`[1,5],[1,6]`或者`[1,6][1,5]`. 可以看到比较例子并没有什么影响.

// 思路2 排序后比较
    	public static boolean insetOrNotInArraysMethod2(int array[][]) {
    		boolean flag = false;
    		int arrayCount = array.length;
    		// 我们这边选择最简单的插入排序.
    		for(int i=0;i<arrayCount;i++) {
    			for(int j=i;j>0;j--) {
    				if(array[j][0]<array[j-1][0]) {
    					swapTwoArray(array,j,j-1);
    				}else {
    					break;
    				}
    			}
    		}
    		// 随后依次判断是否存在左交情况
    		for(int i=1;i<arrayCount;i++) {
    			if(array[i][0]>=array[i-1][0] &&array[i][0] <=array[i-1][array[i-1].length-1]) {
    				flag = true;
    				break;
    			}
    		}
    		return flag;
    	}

--------------------

*  思路3: 穷举.

所谓的穷举就是对于思路1中的两个数组不断迭代判断. 效率比较低. 是一种最先想到的思路.

public static boolean insetOrNotBetweenTwoArrayMethod3(int[] arrayA, int arrayB[]) {
    		// 返回值结果
    		boolean flag = false;
    		if (arrayA.length > 0 && arrayB.length > 0) {
    			for(int i=0;i<arrayA.length;i++) {
    				for(int j=0;j<arrayB.length;j++) {
    					if(arrayA[i]==arrayB[j]) {
    						flag = true;
    						break;
    					}
    				}
    				if(flag) {break;}
    			}
    		}
    		return flag;
    	}

--------------------

*  思路4: hash槽.

对于空间无限大的情况. 可以使用空间换时间的做法. 设置一个`Hash槽`. 将数组存进去, 随后依次遍历即可. 可以使用`Set`和`Map`这样的数据结构都可以.  
对于JDK而言, `HashSet`就是依托于`HashMap`进行实现都. 如果不用记录次数和其他信息, 可以选择`Set`. 如果需要的话可以选择`Map`. 思路相关代码如下所示:

*  思路4 相关代码

public static boolean insetOrNotInArraysMethod4(int array[][]) {
    		boolean flag = false;
    		//
    		HashSet<Integer> set = new HashSet<>();
    		
    		for(int i=0;i<array.length;i++) {
    			for(int j=0;j<array[i].length;j++) {
    				// 判断是否已经存在
    				if(set.contains(array[i][j])) {
    					flag = true;
    					break;
    				}else {
    					// 不然将其放入
    					set.add(array[i][j]);
    				}
    			}
    			if(flag) {break;}
    		}
    		return flag;
    	}

--------------------

### 测试用例 ###

*  Case1 空二纬数组. `[]`
 *  Case2 单个二维数组. `[[1,5]]`
 *  Case3 存在头节点相等的数组. `[[2,4],[2,9]]`
 *  Case4 存在尾节点相等的数组. `[[3,4],[4,4]]`
 *  Case5 正常测试用例.`[[1,6], [5,9],[16,30],[8,10]]`

使用`Junit`测试. 测试用例代码如下所示:

@Test
    	public void testCase() {
    		// * Case1 空二纬数组. `[]`
    		int testArray1[][] = new int[0][];
    		boolean result1 = insetOrNotInArraysMethod1(testArray1);
    		Assert.assertEquals(result1,false);
    		
    		// * Case2 单个二维数组. `[[1,5]]`
    		int testArray2[][] = new int[1][];
    		testArray2[0] = new int[]{1,2,3,4,5};
    		boolean result2 = insetOrNotInArraysMethod1(testArray2);
    		Assert.assertEquals(result2,false);
    
    		// * Case3 存在头节点相等的数组. `[[2,4],[2,9]]`
    		int testArray3[][] = new int[2][];
    		testArray3[0] = new int[]{2,3,4,5};
    		testArray3[1] = new int[]{2,3,4,5,6,7,8,9};
    		boolean result3 = insetOrNotInArraysMethod1(testArray3);
    
    		Assert.assertEquals(result3,true);
    
    
    		// * Case4 存在尾节点相等的数组. `[[3,4],[4,4]]`
    		int testArray4[][] = new int[2][];
    		testArray4[0] = new int[]{3,4};
    		testArray4[1] = new int[]{4};
    		boolean result4 = insetOrNotInArraysMethod1(testArray4);
    		Assert.assertEquals(result4,true);
    
    
    		// * Case5 正常测试用例.`[[1,6], [5,9],[16,30],[8,10]]`
    		int testArray5[][] = new int[4][];
    		testArray5[0] = new int[]{1,2,3,4,5,6};
    		testArray5[1] = new int[]{5,6,7,8,9};
    		testArray5[2] = new int[]{16,17,18,19,20,21,22,23,24,25,26,27,28,29,30};
    		testArray5[3] = new int[]{8,9,10};
    		boolean result5 = insetOrNotInArraysMethod1(testArray5);
    		Assert.assertEquals(result5,false);
    
    	}

--------------------

### 延伸: ###

*  1.不允许改变原数据结构怎么办？  
    使用第一种办法. 或者拷贝空间.
 *  2.不允许使用拷贝空间怎么办?  
    使用第一种办法.
 *  3.需要记录其中所有相交的数组的下标, 应该如何操作？  
    使用第一种办法. 将返回值记录到一个数组内即可.

--------------------

### Reference ###

\[1\]. [java中数组的初始化及操作][java]  
\[2\]. \[字节面试 20200713\]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70]: /images/20230208/f02f9c66dfec490bae6332a5fc9aa73f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 1]: /images/20230208/8f73322bc3e64e3b9fdd29a7e0286dc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 2]: /images/20230208/ef1756badee04ad893a13edb3088deaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0MTYxMDE_size_16_color_FFFFFF_t_70 3]: /images/20230208/6c2b11a82fd14e3593f9a5bd4ff3cbd1.png
[java]: https://jingyan.baidu.com/article/84b4f565076f2620f6da3288.html