[剑指Offer] Day 04

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

解题思路:比较简单的做法是依次遍历,然后存HashMap。(时间、空间复杂度均为O(N)) 如果要求空间复杂度为O(1),则可以利用题目数据的特点,使用「交换位置法」和「置负数」法。

这里使用了「交换位置法」。依次遍历遍历数组,若当前的值与下标不相同,则将其与「当前值为下标」的数字相互交换,若这两个数字是相同的,则直接返回。注意,交换完成后仍然继续判断当前位置,直到下标和值相同,再把位置后移。

若遍历完数组,则说明不存在相同数字,返回-1。(按照题意不会出现这种情况)

时间复杂度:O(N)

空间复杂度:O(1)

class Solution {
    fun findRepeatNumber(nums: IntArray): Int {
        var pos = 0
        while (pos < nums.size) {
            if (nums[pos] == pos) {
                pos++
                continue
            }

            if (nums[nums[pos]] == nums[pos]) {
                return nums[pos]
            }

            val tmp = nums[pos]
            nums[pos] = nums[tmp]
            nums[tmp] = tmp
        }
         return -1
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

解题思路:这题太简单了,就不解释了。

时间复杂度:O(N)

空间复杂度:O(1)

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var count = 0
        for (num in nums) {
            if (num == target) {
                count++
            }
        }
        return count
    }
}

剑指 Offer 53 - II. 0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

解题思路:依照题目特性,遍历数组时,若某个位置的值与下标不相同,说明缺了这个数,直接返回。若遍历完成,说明缺了最后一个数字,返回数组长度即可。

时间复杂度:O(N)

空间复杂度:O(1)

class Solution {
    fun missingNumber(nums: IntArray): Int {
        for (pos in 0 until nums.size) {
            if (nums[pos] != pos) {
                return pos
            }
        }
        return nums.size

    }
}
展示评论