每日一题9

Question

1.有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里，请找出丢失的数字。2.给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。都是很经典的问题，不要谷歌百度哦。昨天没发，今天补上

Answer 1

1. 求和相减
2. HashMap

Answer 2

1.sum(1+..+n)-sum(1+..n-1)
2.线性时间常数空间 不懂 
坐等答案

Answer 3

1.把1到n相加的值减去（n-1）个数的和，就知道丢失的那个数了
2.for(int i=0;i<len;i++)if(data[i]%2==1)就是答案

Answer 4

问题二，使用HashMap第一次遍历求出出现的奇偶次，第二次遍历求出出现奇数次的，复杂度是O(2n)，即O(n)，所以仍然是线性的

Answer 5

第一题：int n_sum=n*(n-1)/2;
for(int i=0;i<a.length;i++)
    n_sum-=a[i];
return n_sum;
第二题：int n=a[0];
for(int i=1;i<a.length;i++)
    n^=a[i];
return n;

Answer 6

第一个sum就不写了，
第二个：
    int x = 0;
    for (int i = 0; i < array.length; i++) {
      x ^= array[i];
    }
    System.out.println(x);

Answer 7

一样处理，float也是32bits依样葫芦将每个bit放到对应的int的bit上去，当作int处理。double->long
    float[] array = new float[] {
        11.23f, 11.23f, 33.555f, 33.555f, -55.01f, -55.01f, 99.999f, 99.999f, 99.999f, 99.999f, -1.9876f
    };
    int x = 0;
    for (int i = 0; i < array.length; i++) {
      int y = Float.floatToIntBits(array[i]);
      x ^= y;
    }
    float result = Float.intBitsToFloat(x);
    System.out.println(result);

Answer 8

package CSDN;/**
 * 有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里，请找出丢失的数字。
 * 
 * @author xqh
 * 
 */
public class FindLostDigital {
public static void main(String[] args) {
int[] arr = { 1, 9, 8, 6, 3, 2, 5, 7 };
System.out.println("丢失的数为：" + find(arr, arr.length + 1));
} /**
 * 求和相减
 * 
 * @param arr
 *            数组
 * @param n
 *            数组原来的长度
 * @return 丢失的数
 */
private static int find(int[] arr, int n) {
int sum = n * (n + 1) >> 1; // 1到n的和
for (int i = 0; i < arr.length; i++)
sum -= arr[i]; // sum - 数组所有元素之和
return sum; // 返回数组丢失的数
}}

Answer 9

//nums 中表示的为 1 - nums.length + 1 中减少了一个数
public static int method1(int[] nums){
int result = 0;
for(int i = 0; i < nums.length; i++){
result ^= i + 1;
result ^= nums[i];
}
return result^nums.length + 1;
}

//nums 中只有一个数的个数为奇数，其他偶数
public static int method2(int[] nums){
int result = 0;
for (int i = 0; i < nums.length; i++) {
result ^= nums[i];
}
return result;
}

Answer 10

 n^=a[i];
请问是什么意思？

Answer 11

那就补充一下，第一题sum的话其实不用考虑溢出问题，因为溢出之后还会溢回来的。

Answer 12

弄一个辅助数组int b[]=new int[n],所有元素初始化为零,扫描原数组a[]，若a[i]=j,令b[j]++
然后根据b中元素来判断

Answer 13

第一个在编程珠玑第二版第一章上有：只需n位空间，初始全部置0，然后依次读取这n个数，并将对应的位置1.最后为0的那位就是缺失的数。
这种方法在java的枚举类型的实现中也用到了。