将新元素插入到已排序的数组中
程序员文章站
2024-03-22 12:08:16
...
条件:
- 旧数组元素为升序排列且内容无重复
要求:
- 将新元素插入到该数组中
- 保证返回的数组不能有重复元素
初步实现
fun insert(old: Array<Int>, newValue: Int): Array<Int> {
val len = old.size + 1
val newArr = Array(len) { 0 }
var l = 0
var get: Int
var bigger = newValue
while (l < old.size) {
get = old[l]
if (get == newValue) return old
if (get < newValue) {
newArr[l] = old[l]
} else {
newArr[l] = bigger
bigger = get // 遍例旧的数组,总是保存较大的值
}
l++
}
newArr[len - 1] = bigger
return newArr
}
改进后
/**
* 将整数插入到排好序的数组中,如果是重复的元素,则返回旧的数组
* @return 并返回新的数组
*/
fun insert(old: Array<Int>, newValue: Int): Array<Int> {
val len = old.size + 1
val newArr = Array(len) { 0 }
var l = 0
var get: Int
var bigger = newValue
while (l < old.size) {
get = old[l]
if (get == newValue) return old
newArr[l] = Math.min(get, bigger) // 将比较的代码优化后
bigger = Math.max(get, bigger) // 总是记录较大的值
l++
}
// 最旧的数组loop结束后,最大的那个值会保存在bigger中
newArr[len - 1] = bigger
return newArr
}
将难度进一步增加
条件:
- 原数组为升序排列的有序数组,但是其中存在重复元素;
要求:
- 将新元素插入到该数组中
- 保证返回的数组要将重复元素移除
/**
* 旧数组为升序且包含重复元素的数组
* @return 返回插入新元素后的新数组,且过滤掉旧数组中重复的元素
*/
fun insertAndFilter(old: Array<Int>, newValue: Int): Array<Int> {
val newArr = Array(old.size + 1) { 0 }
var l = 0 // 标记旧数组
var i = 0 // 标记新数组
var get: Int
var bigger = newValue
while (l < old.size) {
get = old[l]
// 总是与前一个元素比较,相同则continue
if (l > 0 && old[l - 1] == get) {
l++
continue
}
if (get == bigger) {
l++
continue
}
newArr[i] = Math.min(get, bigger)
bigger = Math.max(get, bigger)
l++
i++
}
newArr[i] = bigger
var finalArr = Array<Int>(i + 1) { 0 }
System.arraycopy(newArr, 0, finalArr, 0, finalArr.size)
return finalArr
}
- NOTE:
- old中有重复元素,因此如果只用一个索引值,则会出现一些问题
例如: old = 1,2,3,3,5 new=4
只用一个Flag: 结果会是 1,2,3,0,4,5
总结:
算法不可能一步到最优解,先将功能实现,再逐步优化,提纯
推荐阅读
-
将新元素插入到已排序的数组中
-
在给定的一维已排序(升序)数组中寻找插入一个元素的位置
-
数据结构二分法-给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
-
将数据插入到MySQL表中的详细教程
-
将数据插入到MySQL表中的详细教程
-
sql将一个表中的数据插入到另一个表中的方法
-
将excel表格插入到word中让表格以对象的形式存在
-
sql将一个表中的数据插入到另一个表中的方法
-
C#中怎样将数组的顺序打乱随机排序
-
Aspose.Words 将word2中的内容插入到word1中的指定位置