preface

Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

Their thinking

Idea 1: Use a hash table (space complexity is not sufficient)

  • The key is represented as the element of the array, and the value is represented as the number of occurrences
// Method 1: Use Map data structures
var singleNumbers = function(nums) {
    const m = new Map(a);for (let v of nums) {
        if (m.has(v)) {
            m.set(v,m.get(v) + 1)}else {
            m.set(v,1);
        }
    }
    result = [];
    for (let v of m) {
        if (v[1= = =1) {
            result.push(v[0])}}console.log(result);
    return result;
};
Copy the code

Idea 2: Use bitwise operations (multiple for loops: insufficient space complexity)

  • Because they say that all but two digits occur twice, and if they occur twice, the xOR operation is 0, so the value of all the xor traverses must be the two digits that occur only once.
  • According to the result of all traversal of xor, for example, 0111. From the last digit 1, it can be seen that the last digit of these two numbers that only appear once must be different, so we grouped them according to this feature.
  • Those whose last digit is 1 are divided into group 1, and those whose last digit is 0 are divided into group 1.
  • The two groups perform xor separately, and the resulting value is then returned as the final result. You can do it on paper.
// Use the bit method
var singleNumbers = function(nums) {
    let temp = 0;
    let temp2 = 0;
    let temp3 = 0;
    for (let v of nums) {
        temp = temp ^ v;
    }
    let temp1 = temp.toString(2);
    let flag = 1;
    for (let i = temp1.length-1; i >=0; i--) {console.log(temp1[i]);
        if (temp1[i] === '0') {
            flag = flag + 1;
        } else {
            break; }}// Iterate over each array, converting the values in the array to binary
    const result = []
    for (let v of nums) {
        result.push(v.toString(2));
    }
    console.log(result);
    let arr1 = [];
    let arr2 = [];
    for (let v of result) {
        if (v[v.length-flag] === '1') {
            arr1.push(v);
        } else{ arr2.push(v); }}console.log(flag);
    console.log(arr1);
    console.log(arr2);
    for (let i in arr1) {
        arr1[i] = parseInt(arr1[i],2)}for (let i in arr2) {
        arr2[i] = parseInt(arr2[i],2)}console.log(arr1);
    console.log(arr2);
    for (let v of arr1) {
        temp2 = temp2 ^ v;
    }
    for (let v of arr2) {
        temp3 = temp3 ^ v;
    }
    console.log(temp2,temp3);
    return [temp2,temp3];
};
Copy the code

Final solution (in line with the title)

  • Bit operation
  1. The first thing you do is you xor all the elements of the array, and you get the value from right to left where the first 1 is going to be two different places where the elements occur only once.
  2. Use variables to record the position of the first 1 from right to left.
  3. By summing the variables obtained in step 2 with each element in the array, you can divide the array into two groups
  4. Each of these two groups does the xor, gets two values and then returns the number that they want to appear only once.

code

var singleNumbers = function(nums) {
    let temp = 0;
    let a = 0;
    let b = 0;
    for (let v of nums) {
        temp = temp ^ v;
    }
    console.log(temp);
    // Determine which digit from right to left is 1
    let One_Location = 1;
    while ((temp & One_Location) === 0) {
        One_Location = One_Location << 1;
    }
    for (let v of nums) {
        if ((One_Location & v) === 0) {
            a = a ^ v;
        } else{ b = b ^ v; }};return [a,b];
};
Copy the code