来自 澳门金莎娱乐手机版 2019-11-14 16:49 的文章
当前位置: 金沙澳门官网网址 > 澳门金莎娱乐手机版 > 正文

澳门金莎娱乐手机版:【LeetCode OJ 136】Single Num

【LeetCode OJ 136】Single Number

题目:Given an array of integers, every element appearstwiceexcept for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题思路:题意为:给定一个数组,只有三个因素现身了一回,其余成分都冒出了五遍,搜索极度只现身贰次的数。能够遍历数组,分别举行异或运算。

注:异或运算:相像为0,区别为1。遍历并异或的结果正是那些只现出了二遍的数。

演示代码:

public class Solution 
{
 public int singleNumber(int[] nums) 
 {
  int result=nums[0];
  for (int i = 1; i < nums.length; i++)
  {
   result^=nums[i];
  }
  return result;
 }  
}

OJ 136】Single Number 题目:Given an array of integers, every element appearstwiceexcept for one. Find that single one. Note: Your algorithm should have a linear ru...

137 Single Number II

LeetCode很风趣,出了1事后恐怕还恐怕有2,3都以变体,难度会追加,有时候思路完全不平等。

澳门金莎娱乐手机版 ,Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

其一说真话也是很难想到的,不过照旧遵照的位运算。
给出discuss中头名的答案:

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

本条解法研商一下,大致思路正是:
叁个数现身第一次的时候存在ones中,现身第一遍的时候存在twos中,现身第一回的时候在ones中被清0。所以最终保留的便是现身三遍的数。

  1. Single Element in a Sorted Array

地点大器晚成题其实已经很干燥了,可是那风姿浪漫题很有趣。

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

** Note** : Your solution should run in O(log n) time and O(1) space.

交付三个业已排序过的数组,除了一个数只现出了叁遍,其余的数都冒出了五遍。
其实用137题的写法也是能够的。
可是大家浪费了它业已排序过那么些条件了。
再看看复杂度给的是O(lgn)
十分轻易想到的是二分

public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length / 2;
        while (left < right) {
           int mid = left + (right - left)/2; 
            if (nums[mid * 2] == nums[mid * 2 + 1]) {
               left = mid+1;
           }
           else {
               right = mid;
           }
        }
        return nums[left * 2];
    }

本文由金沙澳门官网网址发布于澳门金莎娱乐手机版,转载请注明出处:澳门金莎娱乐手机版:【LeetCode OJ 136】Single Num

关键词: