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

找出数组中重复的数字。

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

示例:

输入:

[2, 3, 1, 0, 2, 5, 3]

输出:

2 或 3

限制:

2 <= n <= 100000

方法一:暴力求解

function findRepeatNumber($nums) {
    $count = 0;
    for($i = 0; $i < count($nums); $i++){
        foreach($nums as $key => $value){
            if($value === $i){
                if($count > 0){
                    return $value;
                }else{
                    $count++;
                }
            }
        }
        $count = 0;
    }
    return false;
}

暴力求解就是直接双重循环,遍历数组中的每个元素查找是否在数组中有相同的元素
– 时间复杂度是 O(n^2)
– 空间复杂度是 O(1)
数组长度越大,效果越差

方法二:排序比较

function findRepeatNumber($nums) {
    sort($nums);
    for($i = 0; $i < count($nums); $i++){
        if($nums[$i] === $nums[$i+1]){
            return $nums[$i];
        }
    }
    return 0;
}

先对数组进行排序,然后进行遍历,相邻两个元素如果相等,直接返回
– 时间复杂度是 O(n)
– 空间复杂度是 O(n)

方法三:原地置换

function findRepeatNumber($nums){
    for ($i = 0; $i < count($nums); $i++){
        while ($i != $nums[$i]){
            if($nums[$i] == $nums[$nums[$i]]){
                return $nums[$i];
            }
            // 将目标值保存起出来
            $temp = $nums[$nums[$i]];
            // 目标值存为当前值
            $nums[$nums[$i]] = $nums[$i];
            // 当前值设为目标值的值
            $nums[$i] = $temp;
        }
    }
    return -1;

原地置换,理论上,整个数组下标等于下标里的值,如果不相等,就把当前元素的下标放到正确的位置,一边排序一边比较,如果发现有相等的,直接返回。

惭愧,只想到第一第二种方法

学习链接点我

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注