使用双指针方法从已排序数组中删除重复项的 Golang 程序
在这篇 Golang 文章中,我们将介绍使用迭代方法和优化的迭代方法使用双指针方法从已排序数组中删除重复项。数组是具有相同数据类型的元素集合,按照索引或下标访问,并以连续的内存块排列。
已排序数组是一个按照特定顺序排列元素的数组,例如按升序或降序排列。
使用迭代方法的双指针方法
在此方法中,我们将定义一个使用迭代方法的 duplicatesRemove() 函数,该函数用于使用双指针方法从已排序数组中删除重复项。
算法
- 第 1 步: - 首先,需要导入 fmt 包。
-
第 2 步: - 启动主函数 main()。在 main() 函数内,初始化已排序数组。
-
第 3 步: - 现在,调用 duplicatesRemove() 函数并将数组传递给它。
-
第 4 步: - 进一步使用 fmt.Println() 函数打印在删除重复项后的结果更新数组。
-
第 5 步: - 现在,创建一个接收整数数组的 duplicatesRemove() 函数。此函数将在从初始数组中删除重复项后返回一个整数数组。
-
第 6 步: - 该函数首先检查数组的长度是否小于 2。如果是,则返回初始数组,因为无法从长度小于 2 的数组中删除重复项。
-
第 7 步: - 现在,将两个指针 i 和 j 初始值设为 0 和 1。比较 i 和 j 的位置和元素。
-
第 8 步: - 最后,它返回包含仅到 i + 1 位置的唯一元素的初始数组的一个切片。
示例
以下是使用迭代方法和双指针方法从已排序数组中删除重复项的 Go 语言程序
package main
import "fmt"
func main() {
arr := []int{10, 20, 20, 20, 30, 30, 30, 40, 40}
fmt.Println("Initial array:", arr)
arr = duplicatesRemove(arr)
fmt.Println("Updated array after removing duplicates:", arr)
}
func duplicatesRemove(arr []int) []int {
n := len(arr)
if n < 2 {
return arr
}
i, j := 0, 1
for j < n {
if arr[i] == arr[j] {
j++
} else {
i++
arr[i] = arr[j]
j++
}
}
return arr[:i+1]
}
输出
Initial array: [10 20 20 20 30 30 30 40 40]
Updated array after removing duplicates: [10 20 30 40]
使用优化迭代方法的双指针方法
在此方法中,我们将定义一个使用优化的迭代方法的 duplicatesRemove() 函数,该函数用于使用双指针方法从已排序数组中删除重复项。 算法
- 第 1 步: - 首先,需要导入 fmt 包。
-
第 2 步: - 启动主函数 main()。在 main() 函数内,初始化已排序数组。
-
第 3 步: - 现在,调用 duplicatesRemove() 函数并将数组传递给它。
-
第 4 步: - 进一步使用 fmt.Println() 函数打印在删除重复项后的结果更新数组。
-
第 5 步: - 现在,创建一个接收整数数组的 duplicatesRemove() 函数。此函数将在从初始数组中删除重复项后返回一个整数数组。
-
第 6 步: - 该函数首先检查数组的长度是否小于 2。如果是,则返回初始数组,因为无法从长度小于 2 的数组中删除重复项。
-
第 7 步: - 现在,将两个指针 i 和 j 初始化值设为 0 和 1。计数变量 k 初始化值设为 0。
-
第 8 步: - 该函数使用 for 循环遍历数组,并比较 i 和 j 的位置和元素,以找到重复项。如果找到了一个重复项,则将 k 指向的位置的祖先元素和 j 指向的位置的元素相等。如果没有找到重复项,则将 k 的下一个位置的元素设置为 j 的元素。然后,将 i、j 和 k 的下一个位置设置名为 k + 1 的位置。最后,返回数组中的前 k + 1 个元素。
示例
以下是使用优化的迭代方法和双指针方法从已排序数组中删除重复项的 Go 语言程序
package main
import "fmt"
func main() {
arr := []int{10, 20, 20, 20, 30, 30, 30, 40, 40}
fmt.Println("Initial array:", arr)
arr = duplicatesRemove(arr)
fmt.Println("Updated array after removing duplicates:", arr)
}
func duplicatesRemove(arr []int) []int {
n := len(arr)
if n < 2 {
return arr
}
i, j, k := 0, 1, 0
for j < n {
if arr[i] == arr[j] {
j++
} else {
k++
arr[k] = arr[j]
i, j = j, j+1
}
}
return arr[:k+1]
}
输出
Initial array: [10 20 20 20 30 30 30 40 40]
Updated array after removing duplicates: [10 20 30 40]
- 第一步 − 首先,我们需要导入 fmt 包。
-
第二步 − 启动 main() 函数。在 main() 函数内部,初始化排序后的数组。
-
第三步 − 现在,调用 duplicatesRemove() 函数并将数组传递给它。
-
第四步 − 然后,使用 fmt.Println() 函数打印经过去重后的结果更新后的数组。
-
第五步 − 现在,创建一个名为 duplicatesRemove() 的函数,它带有一个整数数组。此函数将从初始数组中删除重复项并返回一个整数数组。
-
第七步 − 现在,将两个指针 i 和 j 分别初始化为 0 和 1。比较 i 和 j 的位置和元素。如果它们不相等,则将 i 增加,并将位置 j 处的元素复制到位置 i。然后,增加 j 移动到下一个元素。
-
第八步 − 继续此过程,直到 j 到达数组的末尾。
-
第九步 − 最后,它将返回初始数组的一个切片,其中仅包含 i+1 位置之前的唯一元素。
示例代码
以下是使用两个指针的优化迭代方法从排序后的数组中删除重复项的 go 语言程序。
package main
import "fmt"
func main() {
arr := []int{10, 10, 20, 30, 30, 30, 40, 50, 50}
fmt.Println("Initial array:", arr)
uniqueArr := duplicatesRemove(arr)
fmt.Println("Updated array after removing duplicates:", uniqueArr)
}
func duplicatesRemove(arr []int) []int {
i := 0
for j := 1; j < len(arr); j++ {
if arr[j] != arr[i] {
i++
arr[i] = arr[j]
}
}
return arr[:i+1]
}
输出结果
Initial array: [10 10 20 30 30 30 40 50 50]
Updated array after removing duplicates: [10 20 30 40 50]
结论
我们已经成功编译并执行了使用两个指针的 go 语言程序,用于从排序后的数组中删除重复项,并使用迭代和优化迭代方法以及两个示例。在第一个示例中,我们使用了迭代方法,在第二个示例中,我们使用了优化过的迭代方法。它们使用 for 循环遍历数组,将每个元素与前一个元素进行比较,并在它是重复项时将其删除。