Golang 使用双指针方法找到两个已排序数组的交集

在这篇Go语言文章中，我们将编写程序来使用双指针方法找到两个数组的交集。交集意味着相似性或最常见的元素，而两个数组的交集指的是两个数组之间相似的元素。

语法

func make ([] type, size, capacity)

go语言中的make函数用于创建数组/地图，它接受要创建的变量的类型、大小和容量作为参数

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组片段中添加值。它接受一定数量的参数。第一个参数是我们希望向其添加值的数组，其后是要添加的值。然后该函数会返回包含所有值的最终数组片段。

func range(variable)

range函数用于迭代任何数据类型。要使用它，我们首先需要写上range关键字，后面跟上我们想要迭代的数据类型，然后循环将在变量的最后一个元素之前进行迭代。

sort.Ints()

此函数属于sort包，用于对包含整数值的切片/数组进行排序。

在if-else条件语句中使用两个指针方法

在此方法中，我们将编写一个使用if条件语句来比较数组元素并将交集点添加到切片中以打印输出的Golang程序，以找到两个数组的交集。

步骤

• 步骤 1 - 在程序中导入fmt、main和sort包，其中fmt有助于输入和输出的格式化，main确保程序是可执行程序，sort用于对数组进行排序

• 步骤 2 - 创建一个名为intersect的函数，其中有两个输入参数array1和array2

• 步骤 3 - 使用sort包中的Ints方法对两个数组进行排序

• 步骤 4 - 然后，将变量i和j初始化为0，这些变量指的是数组的索引

• 步骤 5 - 在此步骤中，创建一个空的交集切片，用于存储两个数组的交集点

• 步骤 6 - 遍历array1和array2，检查元素是否相同，将元素添加到交集切片中，并增加i和j变量

• 步骤 7 - 如果第一个数组元素小于第二个数组元素，则增加i变量，否则增加j变量

• 步骤 8 - 最后，将切片返回给外部函数，并在main函数中使用fmt包的Println函数将输出接收并打印在控制台上，其中ln表示换行

示例

下面的Golang程序解释了如何使用if-else条件语句中的两个指针方法来找到两个数组的交集。

package main

import (
   "fmt"
   "sort"
)

func intersect(array1 []int, array2 []int) []int {

   sort.Ints(array1)
   sort.Ints(array2)

   i := 0 
   j := 0 

   var intersection []int

   for i < len(array1) && j < len(array2) {
      // If the elements are the same, add it to the intersection slice
      if array1[i] == array2[j] {
         intersection = append(intersection, array1[i])
         i++
         j++
      } else if array1[i] < array2[j] {
         i++
      } else {
         j++
      }
   }
   return intersection
}
func main() {

   array1 := []int{1, 2, 2, 3}
   array2 := []int{2, 2}

   intersection_points := intersect(array1, array2)

   fmt.Println("The intersection points of the two arrays are:")
   fmt.Println(intersection_points) 
}

输出

The intersection points of the two arrays are:
[2 2]

在频率图中使用双指针方法

在这个方法中，我们将编写一个Golang程序，使用频率图来查找两个数组的交集，频率图将用于计算每个元素的出现次数并存储在映射中。

步骤

• 步骤 1 - 在程序中导入fmt和main包，其中fmt用于输入和输出的格式化，main用于确保程序是可执行的。

• 步骤 2 - 创建一个intersect函数，并传入两个参数array1和array2，在该函数中使用make函数创建一个频率图。

• 步骤 3 - 迭代array1，并计算数组中元素出现的次数，并存储在映射中。

• 步骤 4 - 在这一步中，创建一个交集切片来存储两个数组的交集点。

• 步骤 5 - 接下来，迭代array2，并检查元素的频率是否大于0。

• 步骤 6 - 如果条件满足，将值附加到交集切片中，并递减该值。

• 步骤 7 - 将切片返回给外部函数，并在主函数中使用fmt包的Println函数打印输出，其中ln表示换行。

示例

以下Golang程序说明了如何使用频率图和双指针方法查找两个数组的交集。

package main

import "fmt"

func intersect(array1 []int, array2 []int) []int {

   freq := make(map[int]int)
   for _, value := range array1 {
      freq[value]++    
   }

   var intersection []int

   for _, value := range array2 {
      if freq[value] > 0 {
         intersection = append(intersection, value)
         freq[value]--
      }
   }
   return intersection
}

func main() {
   array1 := []int{1, 2, 2, 3}
   array2 := []int{2, 2}
   intersection_point := intersect(array1, array2)
   fmt.Println("The intersection point of two arrays is:")
   fmt.Println(intersection_point) 
}

输出

The intersection point of two arrays is:
[2 2]

结论

我们使用两个指针的方法编写并执行了查找两个数组交集的程序，使用了两个示例。在第一个示例中，我们使用了条件if-else语句，在第二个示例中，我们使用了一个频率映射来获得输出。