欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

将新元素插入到已排序的数组中

程序员文章站 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

总结:

算法不可能一步到最优解,先将功能实现,再逐步优化,提纯