首页 > 试题广场 >

数组里面没有出现过的数字

[编程题]数组里面没有出现过的数字
  • 热度指数：1262 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为N的正整数数组nums，其中nums[i]的值都在区间[1,n]中，请你找出nums数组在[1,n]范围里面没有出现过的数字，并将它们放在数组里面返回(在数组里面的顺序可以不唯一)

注:本题有时间复杂度为O(n)，空间复杂度为O(1)的解法，返回的数组不计入空间复杂度计算

数据范围:


示例1

输入

[2,1,4,5,1,2]

输出

[3,6]

说明

数组长度为6，那么范围为[1,6]，其中3和6没有在数组里面出现，返回[3,6]
示例2

输入

[1,1]

输出

[2]
算法知识视频讲解
添加回答
Java
wyllyh123456头像 wyllyh123456
java的 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] findDisappearedNumbers (int[] nums) {
        // write code here
        int n = nums.length;
        int size = n;
        //值是1 - n
        //索引是0 - n-1
        for (int i = 0; i < n; i++) {
            int index = nums[i];
            while(index != -1){
                int temp = nums[index - 1];
                nums[index - 1] = - 1;
                index = temp;
                if(index != -1){
                    size--;
                }
            }
        }
        int[] res = new int[size];
        for (int i = 0; i < n; i++) {
            if(nums[i] != -1){
                res[--size] = i + 1;
            }
            if(size == -1){
                return res;
            }
        }
        return res;
    }
}

发表于 2022-01-28 16:45:22 回复(0)
C++
一品统合头像 一品统合
解题的思路应该是：
  1. 遍历数组，对所有出现过的数字进行标记。
  2. 遍历1~n，没有被标记的数字就是未曾出现过的数字。
解题需要的标记仅需要是二值类型的，无需统计数字出现的频数。
因此如果需要达到节省空间的要求，可以设计二值标记的实现方式。
  1. 使用一般哈希表，记录数字是否出现。然后遍历1~n，查询哈希表找出未出现的元素。
  2. 使用同维度的数组mark。对于原数组的元素nums[i]，将mark[nums[i] - 1] 设为 true。遍历mark，将false元素的索引+1，就是缺失的数组。
  3. 和2思路类似，但是就地实现二值标记，即鸽笼原理。对于nums[i]，将nums[nums[i] - 1] 设为负，即负数标记的元素其索引对应的元素出现过。重新遍历找到非负元素，那么其索引+1就是未出现过的元素。时间复杂度2n，空间复杂度O(1)。
  4. 和思路3类似的实现方式，比如将nums[nums[i] - 1]处的元素+n，即按照nums[nums[i] - 1] > n 是否成立作为二值标记。
思路3代码 
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[abs(nums[i]) - 1] > 0) {
                nums[abs(nums[i]) - 1] *= -1;
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                res.push_back(i + 1);
            }
        }

        return res;
    }
};


发表于 2023-05-14 15:31:13 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型一维数组
*/
func findDisappearedNumbers( nums []int ) []int {
    cnt:=map[int]bool{}
    for _,x:=range nums{
        cnt[x]=true
    }
    ans:=[]int{}
    for i:=1;i<=len(nums);i++{
        if _,ok:=cnt[i];!ok{
            ans=append(ans,i)
        }
    }
    return ans
}

发表于 2023-03-09 07:59:11 回复(0)
C
猪猪侠新新酱头像 猪猪侠新新酱 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* findDisappearedNumbers(int* nums, int numsLen, int* returnSize ) {
    // write code here
    int *hash=(int *)calloc(numsLen,sizeof(int));
    int *ans=(int *)malloc(numsLen*sizeof(int));
    for(int i=0;i<numsLen;i++){
        hash[nums[i]-1]=1;
    }
    int count=0;
    for(int j=0;j<numsLen;j++){
        if(hash[j]==0){
            ans[count++]=j+1;
        }

    }
    *returnSize=count;
    return ans;

}

发表于 2022-12-23 22:54:46 回复(0)
Python 3
来牛客玩玩头像 来牛客玩玩 
class Solution:
    def findDisappearedNumbers(self , nums: List[int]) -> List[int]:
        # write code here
        return list(set(range(1, len(nums)+1)) - set(nums))

发表于 2022-07-09 06:25:56 回复(0)
C++
牛客487629784号头像 牛客487629784号 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        // write code here
        //先遍历一遍nums，使得nums[i]上尽可能放i+1
        //最后遍历nums，发现nums[i]!=i+1的就是缺失的元素
        int i=0;
        while(i<nums.size())
        {
            int cur=nums[i];
            if(cur!=(i+1))
            {
                if(nums[cur-1]!=cur)//如果不等，就交换使得nums[cur-1]=cur
                {
                    nums[i]=nums[cur-1];
                    nums[cur-1]=cur;
                }
                else//如果已经相等就移到下一个(当前位置可能缺失)
                {
                    i++;
                }
            }
            else
            {
                i++;
            }
        }
        vector<int> rt;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=i+1)
            {
                rt.push_back(i+1);
            }
        }
        return rt;
    }
};
发表于 2022-06-30 18:20:44 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def findDisappearedNumbers(self , nums: List[int]) -> List[int]:
        # write code here
        s1 = set(nums)
        s2 = set(range(1,len(nums)+1))
        return list(s2-s1)

发表于 2022-04-22 11:31:55 回复(0)
Python 3
牛客961048420号头像 牛客961048420号
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def findDisappearedNumbers(self , nums: List[int]) -> List[int]:
        # write code here
        l=len(nums)
        re=[]
        for i in range(1,l+1):
            if i not in nums:
                re.append(i)
        return re
发表于 2022-04-08 00:37:57 回复(0)
Java
雷欧尼桑头像 雷欧尼桑
时间复杂度为O(n)，空间复杂度为O(1)的解法 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] findDisappearedNumbers (int[] nums) {
        int n = nums.length;
        int p = 0;
        while (p < n) {
            int idx = nums[p];
            int temp = nums[idx - 1];
            nums[idx - 1] = idx;
            nums[p] = temp;
            if (nums[nums[p] - 1] == nums[p]) {
                p ++;
            }
        }
        int count = 0;
        for (int i = 0; i < n; i ++) {
            if (nums[i] != i + 1) {
                nums[count ++] = i + 1;
            }
        }
        return Arrays.copyOfRange(nums, 0, count);
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

发表于 2022-03-05 22:03:42 回复(0)
Java
_王泥煤头像 _王泥煤
java的 
    public int[] findDisappearedNumbers (int[] nums) {
        // write code here
        int cnt = 0;
        for(int i = 0; i < nums.length; ++i) {
            while(nums[i] > 0 && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
            if(nums[i] > 0 && nums[i] != i + 1) {
                nums[i] = -1;
                ++cnt;
            }
        }
        int[] ans = new int[cnt];
        int idx = 0;
        for(int i = 0; i < nums.length; ++i) {
            if(nums[i] < 0) {
                ans[idx++] = i + 1;
            }
        }
        return ans;
    }


发表于 2022-02-24 22:30:51 回复(0)
Python 3
lllllllollllll头像 lllllllollllll
class Solution:
    def findDisappearedNumbers(self , nums: List[int]) -> List[int]:
        # write code here
        target = set([i for i in range(1,len(nums)+1)])
        s_nums = set(nums)
        res = list(target-s_nums)
        return res
发表于 2022-01-26 23:23:46 回复(0)
Python 3
ALmone头像 ALmone
class Solution:
    def findDisappearedNumbers(self , nums: List[int]) -> List[int]:
        # write code here
        num=set(nums)
        shu=[]
        for j in range(1,len(nums)+1):
            if j not in num:
                shu.append(j)
        return shu
发表于 2022-01-19 10:33:44 回复(0)
C++
大神带我上分啊头像 大神带我上分啊 
vector<int> findDisappearedNumbers(vector<int>& nums) {
        set<int> tmp;
        vector<int> res;
        for (int i = 1; i <= nums.size(); i++)
        {
            tmp.insert(i);
        }
        for (auto p : nums)
        {
            if (tmp.find(p) != tmp.end())
            {
                tmp.erase(p);
            }
        }
        for (auto p : tmp)
        {
            res.push_back(p);
        }
        return res;
    }

发表于 2022-01-17 20:46:17 回复(1)
提交观点

问题信息

哈希
上传者：牛客301499号
难度：
13条回答 1502浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号