输入1~n共n个数,打乱后随机删除一个,找出删除的那个数,不许排序 && 不使用其它变量,实现两个数字的交换 |
您所在的位置:网站首页 › 一组数字随机打乱顺序怎么算出来的 › 输入1~n共n个数,打乱后随机删除一个,找出删除的那个数,不许排序 && 不使用其它变量,实现两个数字的交换 |
输入1~n共n个数,打乱后随机删除一个,找出删除的那个数(不许排序)
对于删除一个数,大概有四种方法: (1)用1+2+...+n减去当前输入数据的总和。时间复杂度:O(n) 空间复杂度:O(1) 【容易溢出】 (2)用1*2...*n除以当前输入数据的总积。时间复杂度:O(n) 空间复杂度:O(1) 【容易溢出】 (3)用1^2^...^n的结果在逐个异或当前输入数据。时间复杂度:O(n) 空间复杂度:O(1) (4)对输入数据进行Hash,然后从头到尾遍历一次。时间复杂度O(n) 空间复杂度O(n) 个人认为第三种最为精妙的,因为相同的数取异或为0,0^0为0,所以最终按照该方法得到的数就是缺失的那个数。 另外第四种使用哈希一遍时间复杂度需要O(n),但是空间复杂度相对要高点。 不使用其它变量,实现两个数字的交换1、使用加减法 void swap(int *a,int *b){ *a = *a + *b; *b = *a - *b; *a = *a - *b; }2、使用乘除法,被除数不能为零 void swap(int a ,int b){ a = a*b; b = a/b; a = a/b; }3、使用异或的方法,只适用于整型变量,不适用于浮点型 int x = 10; //用二进制表示:x=0b1010; int y = 15; //用二进制表示:x=0b1111; System.out.println("x="+x+" y="+y); x = x^y; //x^y= 0b1010^0b1111 = 0b0101 y = x^y; //x^y= 0b0101^0b1111 = 0b1010 =10 x = x^y; //x^y= 0b0101^0b1010 = 0b1111 =15 System.out.println("x="+x+" y="+y);此算法能够实现是由异或运算的特点决定的,通过异或运算能够使数据中的某些位翻转,其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次,值不变。(具体参考:异或运算符的4种情况结果比较) |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |