精华内容
下载资源
问答
  • leetcode解题之448. Find All Numbers Disappeared in an Array Java版 (找出缺少数字

    448. Find All Numbers Disappeared in an Array

    Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

    Find all the elements of [1, n] inclusive that do not appear in this array.

    Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

    Example:

    Input:
    [4,3,2,7,8,2,3,1]
    
    Output:
    [5,6]
    
    不使用额外的空间找出数组中缺少的数字,有几个缺少的就有几个重复的

    import java.util.*;
    
    public class Solution {
    	// 注意有几个缺少的就有几个重复的。总数量不变,标志位解决
    	public List<Integer> findDisappearedNumbers(int[] nums) {
    		List<Integer> ret = new ArrayList<>();
    		for (int i = 0; i < nums.length; i++) {
    			// nums[i]从1到n而下标从0开始,要减去1
    			// temp是从[0,n-1]中少两个,但是有重复
    			int temp = Math.abs(nums[i]) - 1;
    			if (nums[temp] > 0)
    				nums[temp] = -nums[temp];
    		}
    		for (int i = 0; i < nums.length; i++) {
    			if (nums[i] > 0)
    				ret.add(i + 1);
    		}
    		return ret;
    	}
    }

    import java.util.*;
    public class Solution {
    	// 使用set存储出现的元素
    	public List<Integer> findDisappearedNumbers(int[] nums) {
    		List<Integer> ret = new ArrayList<>();
    		// 不能使用list,有重复元素,容易超时
    		Set<Integer> temp = new HashSet<>();
    		for (int i : nums) {
    			temp.add(i);
    		}
    		for (int i = 1; i <= nums.length; i++) {
    			if (!temp.contains(i))
    				ret.add(i);
    		}
    		return ret;
    	}
    
    }

    展开全文
  • leetcode解题之268# Missing NumberJava版 (找出0~N中缺少数字

    268. Missing Number

    Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

    For example,
    Given nums = [0, 1, 3] return 2.

    Note:
    Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

    一个数组包含了从0到n个不同的数字,总共(n+1)个数字,但是其中缺少了一个数字,找出这个数字。题目要求线性时间复杂度,空间复杂度为常数。

    相比于从【0...n】的数组,该数组缺少了一个数,那么计算出【0...n】的数组的和,再减去待计算数组的和,那么缺少的数就出来了。

    public int missingNumber(int[] nums) {
    		// i的范围是0~nums.length-1,算上nums.length(N)就是0~N所有数字
    		int res = nums.length;
    		for (int i = 0; i < nums.length; i++) {
    			res += (i - nums[i]);
    		}
    		return res;
    	}

    // 使用额外的空间
    	public int missingNumber(int[] nums) {
    		Map<Integer, Boolean> map = new HashMap<>();
    		// 初始化0~N为false
    		for (int i = 0; i <= nums.length; i++)
    			map.put(i, false);
    		// 出现的数字把value置为true
    		for (int i = 0; i < nums.length; i++)
    			map.put(nums[i], true);
    		// 返回为false 的数字
    		for (int i = 0; i <= nums.length; i++) {
    			if (!map.get(i))
    				return i;
    		}
    		return -1;
    	}


    展开全文
  • 找出连续数字中缺失的数字

    千次阅读 2019-05-27 19:55:24
    今天有一个业务上的问题,那就是在一串连续的数字找出缺失的数字,我第一想到的就是借助hashmap去实现。如下: int[] array = new int[]{1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; ...

    今天有一个业务上的问题,那就是在一串连续的数字中找出缺失的数字,我第一想到的就是借助hashmap去实现。如下:

    int[] array = new int[]{1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    		Hashtable<Integer, Integer> hasht =
    				new Hashtable<Integer, Integer>();
    		for (int i = 0; i < array.length-1; i++) {
    			hasht.put(array[i], 1);
    		}
    		for (int i = 1; i <= array.length; i++) {
    			if (hasht.get(i) == null) {
    				System.out.println("缺失:" + i);
    			}
    		}

    上述的方式是可以实现查询出想要的结果的。那么还有没有其他的办法实现呢?

    int a[] = {1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    		int b[] = null;
    		b = new int[20];
    
    		for (int i = 0; i < a.length; i++) {
    			b[a[i] - 1] = 1;
    		}
    		for(int i = 0; i < b.length; i++) {
    			if (b[i] == 0) {
    				System.out.println("the lost number is " + (i + 1));
    			}
    		}

    上述的方式就是使用数组来实现。

    也可以借助用1+2+…+n减去当前输入数据的总和,则所得的差就是缺失的那个数。 时间复杂度:O(n) 空间复杂度:O(1)。但n过大时,求和存在溢出问题。

    int a[] = {1, 2, 4, 5, 6,7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    		int sum = 20*(20+1)/2;
    		int t;
    		for(int i=0; i<20-1; i++)
    		{
    			sum = sum - a[i];
    		}
    		System.out.println("sum="+sum);

    二、题目扩展:数组中缺失两个数?
    同样的可以用两种方法: 
    对数据从min~max求和,为S1;并且求出数组中所有元素的和,为S2; 记缺失的数据为a,b。S1-S2=a+b; 那么a、b,一定是一个比(a+b)/2小,一个比它大。再遍历一遍数组,以(a+b)/2为分界线,较小的加为Smin,较大的加为Smax。求出min~(a+b)/2和(a+b)/2~max的和,相减就可以得到两个数了。
     

    展开全文
  • 寻找缺少数字

    2017-05-05 21:09:22
    有100个连续的数字(假设1-100),随机打乱顺序,随机取出这个数字,求最快在这个数组中快速找出缺少数字。  (1)排序后挨个查找  (2)运用hash表存储每个值,再查找  (3)巧妙的计算办法,其实现代码如下: package...

      有100个连续的数字(假设1-100),随机打乱顺序,随机取出一个数字,求最快在这个数组中快速找出缺少的数字。

            (1)排序后挨个查找

            (2)运用hash表存储每个值,再查找

            (3)巧妙的计算办法,其实现代码如下:

    package com.threeTop.www;
    
    import java.util.Random;
    
    /**
     * 寻找缺失的数字
     * @author wjgs
     *
     */
    public class LostNumber {
       
    	
    	/**
    	 * 投机取巧法
    	 * @param array
    	 */
    	public static void find(int []array)
    	{
    		int all=(1+100)*100/2;
    		for(int i=0;i<array.length;i++)
    		{
    			all-=array[i];
    		}
    		System.out.println("缺失的数字为:"+all);
    		
    	}
    	public static void main(String[] args) {
    		//初始化100个数字
    		int []arrayold=new int[100];
    		for(int i=0;i<arrayold.length;i++)
    		{
    			arrayold[i]=i+1;
    		}
    		//打乱排序
    		Random rand=new Random();
    		
    		int t=rand.nextInt(100);
    		//打印缺失的数字
    		System.out.println(arrayold[t]);
    		arrayold[t]=0;
    		LostNumber.find(arrayold);
    
    	}
    
    }
    

        



    展开全文
  • 1-100自然数 找出缺少的数(…

    千次阅读 2014-09-11 15:17:55
    原文地址:找出缺少的数(转)">1-100自然数 找出缺少的数(转)作者:InnerPeace现有1~100共一百个自然数,已随机放入一个有98个元素的数组a[98]。要求写出一个尽量简单的方案,找出没有被放入数组的那2个数,并在...
  • sql语句找出缺少的数

    千次阅读 2008-09-13 02:57:00
    数据表记录,一列的数形如:2,3,4,6,7,8,10,11 1>请用一句sql把中间第一个缺少的数(5)出来 2>请用一句sql把中间所有缺少的数出来(5,9) 1. select (min(num_column) - 1) as num_column from num_table where ...
  • 从0,1,2,...,n这n+1个数中选择n个数,组成有序数组,找出这n个数中缺失的那个数,要求O(n)尽可能小。 示例1 输入 [0,1,2,3,4,5,7] 返回值 6 import java.util.*; public class Solution { /** * 找...
  • 找出重复的那个数字的异或算法

    千次阅读 2015-05-13 14:17:28
    假设你对数组做一次处理,用一种算法找出重复的那个数字,要求不使用大量额外的存储空间(即要求辅助空间为O(1))题目的意思很明显,1001个数字中只有一个数字出现了两次,其余的都是一次。并且不缺少任何数字。...
  • 给定一个连续数组,找出缺失的数字 没什么好讲的,直接上代码吧。 public class FindLostNo{ public static void main(String[] args) { Integer[] test1 = {10,11,12,13,14,16,17,19,20}; int[] test2 = null; ...
  • 比如说[3, 5, 2, 1, 6],3应该在的位置是2,A[2]上的数字是2,不等于3.所以3应该放在2的位置。这时我们应该交换两个数的位置A[0] <=> A[2]; 这样一直搜索下去,最终便是达到临界点,然后结束搜索。最终的结果便是...
  • 1-100个数找出一个缺少的数

    千次阅读 2016-03-25 19:32:02
    sum(1-100)-sum(a0…a99)
  • 举一个例子,1,2,3,4,6,7,8……这个数列中的缺少项就是5,我们的任务就是找出5。 以下操作基于mysql数据库: 1.创建一张表 create table t_increment(id int); 2.插入模拟数据 insert into t_increment...
  • 找出1到n中重复的数字

    千次阅读 2018-08-02 16:22:46
    在数组nums[n + 1]中,数字都是1到n范围内的,那么至少有一个重复数字,找到它。 分析: 这其实是一道比较简单的算法题,但是,如果是面试题,面试官除了用时间复杂度和空间复杂度来约束你...
  • 这次贴上来的代码是解决“找出数列中出现次数最多的数字” 这个问题的,此前在论坛里找到两位前辈的文章,链接如下: 找出数组中出现次数最多的那个数——主元素问题 函数 C++ 找数组a中出现次数最多
  • 原文地址:侯哥小博http://37blog.com/?p=147 function less($start,$end,$arr){ $length=count($arr);... if($end-$start+1==$length){ return "不缺少值"; } if($start!=$arr[0]){ return
  • 1-n中缺失2个数字,O(n)时间内找出它们 VS 2008环境
  • js 找出从1到n的序列中缺少的三个数

    千次阅读 2016-09-11 20:49:03
    // 一个从1到n的正整数序列,从中任意删除三个数,打乱顺序,得到输入的一组数,输出删除的三个数 function main(str) { var input = str.toString().split(' '); for (var i = 0; i ; i++) { ...
  • 数字的和减去数组的和得到的就是缺少数字。但是这个办法的时间复杂度是O(n)。但是我们看到数组是有序的,能不能通过二分法找到数字呢,答案是肯定的。我们可以发现规律,如果数字缺少在数组的前半部分,那么数组...
  • 今天我在修改网页代码时,遇到了一个问题,FireFox下完全没有问题,而在IE中却报JS“缺少标识符 字符串或数字”错误 ,通过在网上搜索,现在终于解决了问题 。 网上搜了一把,果然不少人遇到过这个问题,原因就是:...
  • 算法题:找出不在数组中的最小的那个数字所遇到的问题算法题找出不在数组中的最小的那个数字所遇到的问题 一切的源头 初次探索 二次探索 三次探索 最终探索 主要代码一切的源头一切都源于一个题目:给定一个数组,...
  • 快速找到1到N中缺少的一个数字

    千次阅读 2017-09-08 15:08:04
    传说浙大有一个面试题是要快速找到1到N中缺少的一个数字,有一个很经典的做法是把N-1个数字加和,减去1到N的和,但是当N非常很大的时候,复杂度为O(Nlog(N^2)/32) = O(Nlog(N)/16),和会达到2logN的bit位。...
  • 感觉本次内容没什么好讲的,直接上代码,程序中实现了三种方式,如果有更多方式,请各位小... * 一个无序数组里有 99 个不重复正整数,范围从1到100,唯独缺少一个整数,如何找出这个缺失的整数? */ public st...
  •  * 已知一个数组int[98],该数组里面存储了0~99共100个数字中的98个,数字不重复,请用算法算0~99中缺少的2个数字是哪两个? 要求:数组自己用程序生成,数值介于0~99,相互之间不重复。  */ public class Test...
  • 如其他文章中所写,IE早期浏览器对于格式校验比较严,如果出现SCRIPT1028: 缺少标识符、字符串或数字的错误很大可能是因为多了逗号或者分号什么的,比如: var a = { x: 1, y: 2, }; y:2后面多了个逗号,这在Fire...
  • 首先这是一个奇葩的面试题,自我...给一个数组arr内容是0-99的数字,从中间随机取出一个数字x,剩下的数字在数组arr中递增排序,求:使用最优的方法从数组arr中找到随机取出的x是多少 下面写的是js语法形式 方
  • 找出缺失的整数

    千次阅读 2016-10-14 14:59:21
    漫画算法:找出缺失的整数 原始题目 一个无序数组里,有99个不重复正整数,范围从1到100,唯独缺少一个整数,如何找出这个缺失的整数?
  • 有一个数组data,大小是n-1,其中存储的是1~n中的数字,不重复,即1~n中只有一个数字不在该数组内,找出数字
  • 本题源自leetcode 268 ------------------------------------------------------------- int missingNumber(vector& nums) { int n = nums.size(); int res = n; for(int i = 0;i ;i
  • 找出1-100中缺失的两个数

    千次阅读 2014-03-25 20:50:22
    问如何找出丢失的那两个数?附带条件不能开辟额外的空间。 解题思路:常见的两种解法有:1.计算a+b和a*b的值,然后在解方程求解(但是这样会使得中间某个变量过大)。2.使用bit位来标记。占用13个字节。第二种方法使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,542
精华内容 14,616
关键字:

找出缺少的数字