[剑指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

    }
}