A week really fast ah, in the algorithm to learn the road to take a step, today want to share is to learn the two algorithms only appear once the number and technical sorting

The number that occurs only once

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once. Title source

Example 1:

Input: [2,2,1] output: 1Copy the code

Example 2:

Input: [4,1,2, 2] Output: 4Copy the code

When I first saw this problem I wanted to make an array and I’m just going to write this down, and I’m going to add it up once and I’m going to add it up and then I’m going to reverse the number that’s one

var singleNumber = function(nums) { let len = nums.length; let newArr = []; let result; // Store this value and set count to 0 for(let I = 0; i < len; i++) { let obj = { key:i, count:0, val: nums[i]} newArr.push(obj); } for(let I = 0; i < len; i++) { for(let j = 0 ; j < len; j++) { if(nums[i] == newArr[j].val) { newArr[j].count ++; Newarr.map ((item) => {if(item.count <= 1) {result = item.val; }}); return result; }Copy the code

Later, I read the solution and learned that the method of home is really simple. Finally, the code is as follows

Var singleNumber = function(nums) {var singleNumber = function(nums) { For (let j = 0; j < nums.length; j++){ t ^= nums[j]; } // return t; };Copy the code

So the question comes, what is xor, vaguely remember electrician teacher once taught circuit 01, computing assembly language era is also 01 specific xor, I still do not know the encyclopedia found three characteristics

  1. 0 xor any number = any number
  2. 1 x or any number – take any number inversely
  3. Any number xor itself = set itself to 0

So let t = 0 in this code is interpreted by the first property zero or any number or any number, Let arr = [2,2,1]; let arr = [2,2,1];

Example 2 = 010 421 because it is 2. Example 3 = 011 421 because it is 3 All the ones in the 2's place and all the ones in the 1's carry place have to be 1 in order to be equal to 3 and the exact calculation rule is 011 = 0*2 to the 1 + 2 *2 to the 1 + 1 *2 to the 0 010 010 001 000 010 010 010 111 001 111 001 001 001Copy the code

Let arr2 =,1,2,1,2 [4];

        100 001 010 001 010
        
        100
        000
        100 
            001
            100
            101  
                010
                101
                111
                    001
                    111
                    110 
                        010
                        110
                        100
Copy the code

Count sorting

  1. The reason why I wrote this sentence is because this is the only sentence I remember when I studied it
  2. I think this is a very easy idea to understand and it’s similar to the idea I had in the first question, except that the data is fixed in a certain interval
Function sumSort(arr){function sumSort(arr){let len = arr.length+1; let newArr = []; For (let I = 0; i < len; Let obj = {key: I, count: 0} for(let j = 0; j < len - 1; If (arr[j] == I){obj. Count ++; } } newArr.push(obj); } let result = []; Newarr.map ((item) => {if(item.count) {for(let I = 0; i < item.count; i++) { result.push(item.key) } } }) return result; }Copy the code

This is similar to a table and then put the corresponding data into the corresponding cells, and finally put the data in order one by one out.