《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 463|回复: 4
收起左侧

[算法题] Majority Element最优解看不懂(不是Moore Voting), 求大神指点思路

[复制链接] |试试Instant~ |关注本帖
vegito2002 发表于 2017-6-27 23:48:23 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
代码是 leetcode 提交的时候直接点第一名点出来的. 作者应该是个中国人, 只有代码, 速度确实是第一名1ms, 比moore voting快, 但是原理看不懂, 希望大神指点一下:

  1. /*
  2. Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

  3. You may assume that the array is non-empty and the majority element always exist in the array.
  4. */

  5. public class MajorityElement {
  6.     public int majorityElement(int[] nums) {
  7.         return maj(nums, nums.length);
  8.     }

  9.     public int maj(int[] nums, int n) {
  10.         if (n == 1 || n == 2) return nums[0];
  11.         int p = 0;
  12.         for (int i = 0 ; i < n; i = i + 2) {
  13.             if (i == n - 1 || nums[i] == nums[i + 1]) {
  14.                 nums[p++] = nums[i];
  15.             }
  16.         }
  17.         return maj(nums,p);
  18.     }
  19.        
  20.     public static void main(String[] args) {
  21.         MajorityElement tester = new MajorityElement();
  22.         int[] input1 = {1,2,1,3,1,4,1};
  23.         System.out.println(tester.majorityElement(input1));
  24.     }
  25. }
复制代码
comment里面有题目简介.

主要是不知道这个算法背后的原理是什么? 为什么这个算法就是对的? 和一个认识的大神讨论过, 不太理解这个算法的 correctness, 但是就是举不出反例.

评分

1

查看全部评分

magicsets 发表于 2017-6-28 08:30:48 | 显示全部楼层
本帖最后由 magicsets 于 2017-6-28 08:52 编辑

楼主引用的这个解法适合1,2,1,2,1,2,1,2,...这种交替型的workload。如果输入数据是1,1,1,1,...,2,2,2,2,...这种连续一大段都是同一个数的workload,那么这种算法会相对比较慢。所以它的速度最快大概是因为LeetCode的测试数据比较对它胃口...

要证明其正确性,本质上是要证明如下定理:
定理1:给定一个长度为n>2的数组nums[0] ... nums[n-1],其中包含有Majority Element K。那么执行完所给代码的第15~20行后,nums[0] ... nums[p-1]中包含Majority Element K。

然后每次调用maj都有p <= n/2,递归调用就行了,worst case下要递归log(n)层(例如:所有n个元素都是K的情况)。

下面来证明定理1,我们可以用反证法。
---------------------------------------------------
定理1的证明:
假设执行完所给代码的15~20行后,nums[0] ... nums[p-1]中包含u个K,v = p - u个其他元素,且u <= v(即K不是Majority Element)。

那么,考虑n的奇偶:
Case (1): n为偶数
由17~18行的代码易知原来的nums[0] ... nums[n-1]数组中至多有 S = u*2 + (n/2 - p)个K。
注意到u*2 - p = u - v <= 0,所以S <= n/2,这与前提条件“K在原来的数组中是Majority Element”矛盾。

Case (2): n为奇数
这里再细分为两种情况:
Case (2.1): nums[n-1] == K
    由17~18行的代码易知原来的nums[0] ... nums[n-1]数组中至多有 S = (u-1)*2 + ((n+1)/2 - p)个K。
    那么化简S = (n-3)/2 + (u-v) < (n-1)/2,这与前提条件“K在原来的数组中是Majority Element”矛盾。
Case (2.2): nums[n-1] != K
    由17~18行的代码易知原来的nums[0] ... nums[n-1]数组中至多有 S = u*2 + ((n-1)/2 - p)个K。
    那么化简S = (n-1)/2 + (u-v) <= (n-1)/2,这与前提条件“K在原来的数组中是Majority Element”矛盾。

所以任何情况下假设都不成立,也就是说执行完15~20行后,K在nums[0] ... nums[p-1]中必然是Majority Element。▢
---------------------------------------------------

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

乌云典当记 发表于 2017-6-28 00:34:35 | 显示全部楼层
楼主可以看看这个http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
回复 支持 反对

使用道具 举报

 楼主| vegito2002 发表于 2017-6-28 04:52:35 | 显示全部楼层
乌云典当记 发表于 2017-6-28 00:34
楼主可以看看这个http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

这个算法不是moore voting. moore voting我是懂得. 这个算法比moore voting还快.
回复 支持 反对

使用道具 举报

 楼主| vegito2002 发表于 2017-6-29 04:59:22 | 显示全部楼层
magicsets 发表于 2017-6-28 08:30
楼主引用的这个解法适合1,2,1,2,1,2,1,2,...这种交替型的workload。如果输入数据是1,1,1,1,...,2,2,2,2,... ...

非常感谢你的分享, 你这个 invariant 一点出来就豁然开朗了. 不知道能不能加你一下的个人联系方式? 希望以后有更多的和你学习的机会.

补充内容 (2017-7-3 05:32):
已勾搭上大神
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-20 10:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表