26. Remove Duplicates from Sorted Array

Leetcode 问题: 26. Remove Duplicates from Sorted Array
Categories:
Tags:

题目

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

传入排序过的数字阵列，并移除重複的数字

答案

Golang

func removeDuplicates(nums_list []int) int {
    if len(nums_list) == 0 {
        // 若没有数字资料
        return 0
    }
    // 数字清单长度
    num_list_length := len(nums_list)
    // 最大数字所在索引
    max_num_index := num_list_length -1
    // 最后一个非重複数字索引
    last_none_duplicate_num_index := 0
    // 非重複数字搜寻索引
    non_duplicate_num_finder_index := 0


    for last_none_duplicate_num_index < max_num_index {
        // 最后一个非重複数字索引不是最后一个项目，继续往后找
        for nums_list[non_duplicate_num_finder_index] == nums_list[last_none_duplicate_num_index] {
            // 若持续找到相同的数字，继续往后找，直到数字不同在跳出
            non_duplicate_num_finder_index++

            if non_duplicate_num_finder_index == num_list_length {
                // 找到最后一个项目，非重複的长度为最后一个项目索引 +1
                return last_none_duplicate_num_index + 1
            }
        }

        // 将非重複元素索引往后移动
        last_none_duplicate_num_index++
        // 找到不同的元素了，将找到的不同元素複製到前方
        nums_list[last_none_duplicate_num_index] = nums_list[non_duplicate_num_finder_index]
    }

    return last_none_duplicate_num_index + 1
}

完整程式码

package main

import (
    "fmt"
)

type QuestionList struct {
    Parameter
    Answer
}

// Parameter 是参数
// nums_list 代表第一个参数
type Parameter struct {
    nums_list []int
}

// Answer 是答案
// nums 代表第一个答案
type Answer struct {
    nums int
}


func main() {

    question_list := []QuestionList{
        {
            Parameter{[]int{1, 1, 2}},
            Answer{2},
        },

        {
            Parameter{[]int{0, 0, 1, 1, 1, 1, 2, 3, 4, 4}},
            Answer{5},
        },

        {
            Parameter{[]int{0, 0, 0, 0, 0}},
            Answer{1},
        },
        {
            Parameter{[]int{1}},
            Answer{1},
        },
    }

    fmt.Printf("------------------------Leetcode Problem 26------------------------\n")

    for _, question := range question_list {
        Ans, Param := question.Answer, question.Parameter
        fmt.Printf("【input】:%v  answer:%+v  【output】:%v\n", Param.nums_list, Ans.nums, removeDuplicates(Param.nums_list))
    }

}

func removeDuplicates(nums_list []int) int {
    if len(nums_list) == 0 {
        // 若没有数字资料
        return 0
    }
    // 数字清单长度
    num_list_length := len(nums_list)
    // 最大数字所在索引
    max_num_index := num_list_length -1
    // 最后一个非重複数字索引
    last_none_duplicate_num_index := 0
    // 非重複数字搜寻索引
    non_duplicate_num_finder_index := 0


    for last_none_duplicate_num_index < max_num_index {
        // 最后一个非重複数字索引不是最后一个项目，继续往后找
        for nums_list[non_duplicate_num_finder_index] == nums_list[last_none_duplicate_num_index] {
            // 若持续找到相同的数字，继续往后找，直到数字不同在跳出
            non_duplicate_num_finder_index++

            if non_duplicate_num_finder_index == num_list_length {
                // 找到最后一个项目，非重複的长度为最后一个项目索引 +1
                return last_none_duplicate_num_index + 1
            }
        }

        // 将非重複元素索引往后移动
        last_none_duplicate_num_index++
        // 找到不同的元素了，将找到的不同元素複製到前方
        nums_list[last_none_duplicate_num_index] = nums_list[non_duplicate_num_finder_index]
    }

    return last_none_duplicate_num_index + 1
}

参考资料