The topic of dry

Given an ordered array of integers, where every element appears twice and only one number appears only once, find the number.

Example 1:

Input: [1,1,2,3,3,4,4,8,8] output: 2Copy the code

Example 2:

Input: [3,3,7,7,10,11,11] output: 10Copy the code

Idea 1: A loop

Each time the loop compares the current element with the next one. If they are the same, continue until the end of the loop and return the last element. Otherwise, the current value is returned.

Execution time: 80 ms, beating 83.39% of all JavaScript commits

Memory consumption: 38.6 MB, beating 100.00% of users in all JavaScript commits

 var singleNonDuplicate = function (nums) {
    let length = nums.length;
    if (length == 1) {
      return nums[0]}for (let i = 0; i < length - 1;) {
      if (nums[i] == nums[i + 1]) {
        i = i + 2;
      } else {
        return nums[i]
      }
    }
    return nums[length - 1]};Copy the code

Idea 2: Dichotomy

This problem can still be solved by dichotomy, which is to judge according to our position. If our current position is even position, then judge the boundary of dichotomy according to the comparison with the left and right elements, and the odd position is opposite to the even position.

Draw a picture and analyze it:

Code implementation:

 / * * *@param {number[]} nums
 * @return {number}* /
var singleNonDuplicate2 = function (nums) {
    // Dichotomy
    let mid = 0;
    let min = 0;
    let max = nums.length - 1;
    while (min <= max) {
        mid = Math.floor((min + max) / 2);
        let right = nums[mid + 1];
        let left = nums[mid - 1];
        if(right ! = nums[mid] && left ! = nums[mid]) {return nums[mid] }
        if (mid % 2= =0) {
            if(nums[mid]==right){
                min=mid+1
            }else{
                max=mid-1}}else {
            if(nums[mid]==left){
                min=mid+1
            }else{
                max=mid-1}}}};Copy the code