leetcode-137. Single Number II[很有意思的一道题目]

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

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

题目链接:https://leetcode.com/problems/single-number-ii/

 

这道题目最直接的方法是使用哈希表来解决。

但是使用哈希表是文艺青年的做派。

对于追求极致的大牛来说,这显然还不够。

下面的解法思路是从其它大牛copy来的,简单分析一下:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two, three = 0, 0, 0
        for v in nums:
            two |= one & v
            one ^= v
            three = ~(one & two)
            one &= three
            two &= three
        return one
思路解析:
因为除了一个出现了一次的数,其它数都重复了3次。我们可以想到用
位运算来解决问题。
我们用one记录当前位置之前(包括当前位置)所有数字的各个二进制位
的总数模3等于1 ,同样用two记录当前位置之前(包括当前位置)所有数
字的各个二进制位的总数模3等于2
比如当前数字是3,前面有1与4,那么one会记录3,1,4第1至32位bit
中1出现的次数模3==1的结果,two会记录模3==2的结果。
one&two的结果的某个比特位==1,说明one中的该比特位与two中的
该比特位都是1,那么说明该比特位出现了3次,需要从当前结果中消掉
这些比特位。很简单,one&two按位取反表明不需要去掉的比特位,
那么one&(~(one&two))将one中的出现3次的比特位去掉。
最后剩下只出现一次的数的所有的比特位都在one中记录。那么one肯定
就是那个只出现一次的数。

leetcode-287. Find the Duplicate Number[Floyd算法-龟兔算法]

该题的另一种解法是环检测的方法。

http://keithschwarz.com/interesting/code/find-duplicate/FindDuplicate.python.html

以下为翻译:

这道题(据说)花费了计算机科学界的传奇人物Don Knuth 24小时才解出来。并且我只见过一个人(Keith Amling)用更短时间解出此题。

问题的第一部分 - 证明至少存在一个重复元素 - 是鸽笼原理的直接应用。如果元素的范围是[1, n],那么只存在n种不同的值。如果有n+1个元素,其中一个必然重复。

问题的第二部分 - 在给定约束条件下寻找重复元素 - 可就难多了。 要解决这个问题,我们需要敏锐的洞察力,使问题通过一列的转化,变为一个完全不同的问题。

解决本题需要的主要技巧就是要注意到:由于数组的n + 1个元素范围从1到n,我们可以将数组考虑成一个从集合{1, 2, ..., n}到其本身的函数f。这个函数的定义为f(i) = A[i]。基于这个设定,重复元素对应于一对下标i != j满足 f(i) = f(j)。我们的任务就变成了寻找一对(i, j)。一旦我们找到这个值对,只需通过f(i) = A[i]即可获得重复元素。

但是我们怎样寻找这个重复值呢?这变成了计算机科学界一个广为人知的“环检测”问题。问题的一般形式如下:给定一个函数f,序列x_i的定义为

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

假设函数f从定义域映射到它本身,此时会有3种情况。首先,如果定义域是无穷的,则序列是无限长并且没有循环的。例如,函数 f(n) = n + 1,在整数范围内满足这个性质 - 没有数字是重复的。 第二, 序列可能是一个闭合循环,这意味着存在一个i使得x_0 = x_i。在这个例子中,序列在一组值内无限循环。第三,序列有可能是的“ρ型的”,此时序列看起来像下面这样:

      x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                         ^                       |
                         |                       |
                         +-----------------------+

也就是说,序列从一列链条型的元素开始进入一个环,然后无限循环。我们将环的起点称为环的“入口”。

对于从数组中寻找重复元素这个问题,考虑序列从位置n开始重复调用函数f。亦即从数组的最后一个元素开始,然后移动到其元素值对应的下标处,并且重复此过程。可以得到:此序列是ρ型的。要明白这一点,需要注意到其中一定有环,因为数组是有限的并且当访问n个元素时,一定会对某个元素访问两次。无论从数组的哪一个位置开始,这都是成立的。

另外,注意由于数组元素范围1到n,因此不存在值为0的元素。进而,从数组的第一个元素开始调用一次函数f之后,再也不会回到这里。这意味着第一个元素不会是环的一部分,但如果我们继续重复调用函数f,最终总会访问某个节点两次。从0节点开始的链条与环形相接,使得其形状一定是ρ型。

此外,考虑一下环的入口。由于节点位于环的入口,一定存在两个输入,其对应的函数f的输出值都等于入口元素下标。要使其成立,一定存在两个下标i != j,满足f(i) = f(j),亦即A[i] = A[j]。因而环的入口一定是重复值。

这是由Robert Floyd提出的一个著名算法,给定一个ρ型序列,在线性时间,只使用常数空间寻找环的起点。这个算法经常被称为“龟兔”算法,至于原因下面就明白了。
算法背后的思想是定义两个变量。首先,令c为进入环的链的长度,然后令l为环的长度。接下来,令l'为大于c的l的倍数的最小值。可以得出结论:对于上文定义的任意ρ型序列的l',都有
 
     x_{l'} = x_{2l'}
 
证明实际上非常直观并且具有自明性 - 这是计算机科学中我最喜欢的证明之一。思路就是由于l'至少为c,它一定包含在环内。同时,由于l'是环长度的倍数,我们可以将其写作ml,其中m为常数。如果我们从位置x_{l'}开始(其在环内),然后再走l'步到达x_{2l'},则我们恰好绕环m次,正好回到起点。

Floyd算法的一个关键点就是即使我们不明确知道c的值,依然可以在O(l')时间内找到值l'。思路如下。我们追踪两个值"slow"和"fast",均从x_0开始。然后迭代计算
 
     slow = f(slow)
     fast = f(f(fast))
 
我们重复此步骤直到slow与fast彼此相等。此时,我们可知存在j满足slow = x_j,并且fast = x_{2j}。 由于x_j = x_{2j},可知j一定至少为c,因为此时已经在环中。另外,可知j一定是l的倍数,因为x_j = x_{2j}意味着在环内再走j步会得到同样的结果。最后,j一定是大于c的l的最小倍数,因为如果存在一个更小的大于c的l的倍数,我们一定会在到达j之前到达那里。所以,我们一定有j = l',意味着我们可以在不知道环的长度或者形状的情况下找到l'。

要完成整个过程,我们需要明白如何使用l'来找到环的入口(记为x_c)。要做到这一步,我们再用最后一个变量,记为"finder",从x_0出发。然后迭代重复执行过程:

 
    finder = f(finder)
    slow   = f(slow)
 
直到finder = slow为止。
我们可知:
(1) 两者一定会相遇 
(2) 它们会在环的入口相遇。 
要理解这两点,我们注意由于slow位于x_{l'},如果我们向前走c步,那么slow会到达位置x_{l' + c}。由于l'是环长度的倍数,相当于向前走了c步,然后绕环几圈回到原位。换言之,x_{l' + c} = x_c。另外,考虑finder变量在行进c步之后的位置。 它由x_0出发,因此c步之后会到达x_c。这证明了(1)和(2),由此我们已经证明两者最终会相遇,并且相遇点就是环的入口。

算法的美妙之处在于它只用O(1)的额外存储空间来记录两个不同的指针 - slow指针和fast指针(第一部分),以及finder指针(第二部分)。但是在此之上,运行时间是O(n)的。要明白这一点,注意slow指针追上fast指针的时间是O(l')。由于l'是大于c的l的最小倍数,有两种情况需要考虑。首先,如果l > c,那么就是l。 否则,如果l < c,那么我们可知一定存在l的倍数介于c与2c之间。要证明这一点,注意在范围c到2c内,有c个不同的值,由于l < c,其中一定有值对l取模运算等于0。最后,寻找环起点的时间为O(c)。这给出了总的运行时间至多为O(c + max{l, 2c})。所有这些值至多为n,因此算法的运行时间复杂度为O(n)。

Python程序如下:
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        fast = 0
        slow = 0

        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if slow == fast:
                break

        fast = 0
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]

        return fast

leetcode-287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than
    O(n<sup>2</sup>)

    .

  4. There is only one duplicate number in the array, but it could be repeated more than once.

题目描述:

给定长度为n+1的整形数组,该数组的每一个整数均在[1,n]之间。

假设只有一个重复的数字,请找出该重复数字。

注意:

1.不能修改数组(假设数组只读)

2.空间复杂度为O(1)

3.时间复杂度小于O(n^2)

4.数组中只有一个重复数字,但是它可能重复不止一次。

 

思路:

根据抽屉原理,如果数组中不超过n/2的元素的数目大于n/2,那么重复数字肯定出现在前半段。反之出现在后半段。导致这种结果的原因在于数组只有一个数字是重复的,也就是说n个数字不重复。超过一半的数字处于平均值之下,那么重复数字 只可能在前半部分。

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        right = len(nums)-1
        left = 1


        while left < right:
            mid = left + (right-left)/2
            counter = 0
            for num in nums:
                if num <= mid:
                    counter += 1
            if counter > mid:
                right = mid-1
            else:
                left = mid+1
        return left

leetcode-41.First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given

[1,2,0]

return

3

,
and

[3,4,-1,1]

return

2

.

Your algorithm should run in O(n) time and uses constant space.

题目描述:

给出无序的整数数组,找出第一个缺失的正数。

例如,

[1,2,0] 返回 3

[3,4,-1,1]返回2

算法的时间复杂度不超过O(n)并且使用常量空间。

思路:

题目要求是找到缺失的第一个正数,那么我们只把数组中是正数的元素交换到其在数组中其元素值的位置,比如a[5] = 3,那么将a[5]与a[2]交换。

这样正数都会被放置在其应该处于的位置,而负数以及元素值超过数组长度的数跳过。最后所有的有效正数都会被放置在其对应的位置。

等全部交换完成后从头开始查找第一个元素其元素值与位置不符,返回该元素位置。

Python代码示例:

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if nums[i] != i+1 and nums[i] < len(nums) and nums[i] >= 1 and nums[i] != nums[nums[i]-1]:
                tmp = nums[i]
                nums[i] = nums[tmp-1]
                nums[tmp-1] = tmp
            else:
                i += 1
        print nums
        for i in xrange(len(nums)):
            if i+1 != nums[i]:
                return i+1
        return len(nums)+1

约瑟夫环

普通的解法:构建环然后循环去除元素

int JosephuseCircle(unsigned int n,unsigned int m){
if(n<1||m<1) return -1;
unsigned int i=0;
list<int> l;
for(i=0;i<n;++i)
l.push_back(i);
list<int>::iterator cur = l.begin();
while(l.size()>1){
for(int i=1;i<m;++i){
cur++;
if(cur == l.end())
cur = l.begin();
}
list<int>::iterator next = ++cur;
if(next == l.end())
next = l.begin();
–cur;
l.erase(cur);
cur = next;
}
return *(cur);
}

更高效的解决方法:构建递推公式

  1.  定义关于数据长度n和删除步进m的方程F(n,m),表示在n个数字0,1,…,n-1中每次删除第m个数字后最后剩下的一个数字。
  2. 在n的数字中,第一个被删除的是(m-1)%n,简记为k。那么剩下的n-1个数字是0,1,…,k-1,k+1,…,n-1.并且下一次删除从k+1开始。
  3. 在第二次删除时,数字序列是 k+1,k+2,…,n-1,0,1,…k-1。
  4. 此时的函数F(n,m)的数字序列发生了变化,为了适应该变化我们将此时的F(n,m)记为F'(n-1,m)
  5. 由于F与F’的结果都是最后一个数字,那么F(n,m)=F'(n-1,n)
  6. 然后对第二次的数字序列做映射:

k+1              ===>                       0

k+2              ===>                       1

n-1              ===>                       n-1-k-1=n-k-2

0                  ===>                       n-k-1

1                   ===>                      n-k

k-1                ===>                       n-2

7.从上面得出映射 p(x) = (x-k-1)%n,表示当前映射数字x实际上是F(n,m)中的第(x-k-1)%n个数字。逆映射p^-1(x) = (x+k+1)%n;

8.由于映射后的序列与最初的序列都具有同样的形式即都从0开始,那么仍然可以F(n-1,m)表示。可以得出

F'(n-1,m) = p^-1(F(n-1,m))=映射之前剩下的最后一个数字=[F(n-1,m)+k+1]%n

把k = (m-1)%n带入,那么F(n,m) = F'(n-1,m)=[F(n-1,m)+m]%n

9:上面的公式可以归纳为以下公式:

F(n,m)=0 if  n=1 else [F(n-1,m)+m]%n 

这是一个递归的求解过程,因为最后n=1时有具体的结果不会再继续递归下去。
int JosephuseCircle2(unsigned int n,unsigned int m){
if(n<1||m<1)
return -1;
int last = 0;
for(int i=2;i<=n;++i){
last = (last+m)%i;
}
return last;
}