力扣(LeetCode)448

dreamtecher 发布于2019-08-16 14:24 / 2802人阅读

摘要：题目地址题目描述给定一个范围在数组大小的整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在范围之间没有出现在数组中的数字。示例输入输出解答对原数组做映射，把数字映射到原数组的上，使得为。

题目地址：
https://leetcode-cn.com/probl...
题目描述：
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

解答：
对原数组做映射，把数字i(i>=1,i<=n)映射到原数组的nums[i-1]上，使得nums[i-1]为-1。
然后再扫描一遍数组，如果numsj不为-1，那么j+1就不存在！
java ac代码：

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        
        Listans = new ArrayList(nums.length);
        for(int i = 0;i < nums.length;i++)
        {
            
            int loc = nums[i]-1;
            if(loc != -2)
            while(nums[loc] != -1){
            int temp = nums[loc]-1;    
            nums[loc] = -1;
            loc = temp;
            }
            
        }
        for(int i = 0;i < nums.length;i++)
            if(nums[i] != -1)
                ans.add(i+1);
        return ans;
        
    }
}

云服务器服务器托管力扣 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72974.html

Leetcode PHP题解--D79 448. Find All Numbers…

摘要：题目链接题目分析给定一个到的数组，返回其中缺失的数字。思路用得出到的数字，再用和给定的数组计算差集。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D79 448. Find All Numbers Disappeared in an Array 题目链接 448. Find All Numbers Disappeared in an Array 题目分析给定一个1到n的数组，返回...

X1nFLY 2019-07-01 13:57 评论0 收藏0
力扣(LeetCode)310

摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。题目地址：https://leetcode-cn.com/probl...题目描述：对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...

amuqiao 2019-08-16 16:13 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
力扣(LeetCode)452

摘要：对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。解答这是一道区间覆盖问题，不太好说清楚，利用模板即可。题目地址：https://leetcode-cn.com/probl...题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方...

fanux 2019-08-16 15:20 评论0 收藏0