输入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 办公设备维修网 版权所有 豫ICP备15022753号-3 |