澳门威利斯人_威利斯人娱乐「手机版」

来自 威利斯人娱乐 2019-11-16 06:11 的文章
当前位置: 澳门威利斯人 > 威利斯人娱乐 > 正文

leetcode_single number

leetcode_single number

136 SingleNumber

Given an array of integers, every element appears twice except for one. Find that single one.

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

那一个主题素材很精华,变体也多。
最轻便想到的做法必定会将是开三个HashMap存各类数字现身的次数。
可是供给是O(n)的复杂度,未有额外的上空开辟。
实则自身想很难想到,看了题解之后当先二分之一人的以为是还有这种操作

固然用叁个0和各样成分取异或,多少个数异或自身为0,所以现身五回的数异或今后为0,而现身二次的数则保留了下来。
看代码:

public int singleNumber(int[] nums) {
        int i = 0;
        for (int num : nums) {
            i ^= num;
        }
        return i;
    }

难题汇报:

Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

标题陈说

Given an array of integers, every element appears twice except for one. Find that single one.

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

注:风度翩翩组数各样数都现身两回除了内部有些数,请搜索那个只现出三回的数,不适用额外层空间间。

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中,现身第3回的时候存在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_single number

关键词: 澳门威利斯人 程序员 日记本 leecode解题