快速找出机器故障 - 编程之美1.5


快速找出机器故障 - 编程之美1.5
问题1、已知一个数组,数组中只有一个数据是出现一遍的,其他数据都是出现两遍,我们要把这个数据找出来
方法三、利用异或运算(推荐使用)
思想:将列表中的所有ID异或,之后得到的值即为所求ID
利用异或运算可以得到
 X^X=0   X^Y=Z  X^0=X
  1. X ⊕ X = 0   X ⊕ Y = Z  X ⊕ 0 = X  
  2. 比如说ID为 2 1 2 3 1 要找的ID为3  
  3. 2的二进制为010,1的二进制为001  
  4. 3的二进制为011  
  5. 则2 ⊕1 = 010⊕001= 011   
  6. 011 ⊕2 = 011⊕010=001=1(2⊕1⊕2 = 1)  
  7. 1⊕3 = 001⊕011=010  
  8. 010⊕001=011 = 3  
  9. 最终的结果仍然是那个只出现一次的数  

缺点:前提是只有一个ID出现一次,若出现多次,则不适合
方法四、利用 "不变量" (推荐使用)
利用数学中“不变量”的概念,例如预先保存所有ID之和与所有ID之积。
对于两台机器死机的话,就可以列出如下方程:
x+y=a
xy=b
不过实现上可能会有问题,就是大整数乘法造成算术溢出,可以尝试通过采用平方和来解决。
时间复杂度:O(N)时间,空间复杂度O(1)
问题2、已知一个数组,数组中有两个不同的数据都出现一遍,其他数据都是出现两遍,我们要把这两个数据找出来
题里面是丢失的是两个不同的数据,我们这里两种情况都考虑下
如果缺少的两个数字不相同,
方法:进行异或操作
思路:由于缺少的数不同,则最后异或的结果不为0。
  1. (1)对数组中所有的ID进行异或,结果为a  
  2. (2)我们找到a的二进制表示中,最低一位为1的位置b  
  3. (3)根据b位是否为1,将ID数组中的数分为两个数组,其中一个数组中的b位为1,另一个队列中的b位为0。  
  4. (注意,每个数组中,除了那个只出现一次的数外,其他数都是出现两次的,此时就可以在数组内使用异或操作)  
  5. (4)然后对两个数组,分别进行异或操作,则将得到两个不为0的数字。即为所丢失的两个ID。 
问题1: 找出出现奇数次的两个数
http://bylijinnan.iteye.com/blog/1573337
void findRepeatedTwoNumbers(int a[], int n, int& no1, int& no2)  
{  
    int i, j, temp;  
    //计算这两个数的异或结果,  
    temp = 0;  
    for (i = 0; i < n; i++)  
    {
        temp ^= a[i];  
    }    
    // temp的值现为两个出现奇数次的数的异或
    // 找第一个为1的位  
    for (j = 0; j < sizeof(int) * 8; j++)
    {  
        if (((temp >> j) & 1) == 1)  
        {
            break;
        }  
    }    
    // 第j位为1,说明这两个数字在第j位上是不相同的  
    // 由此分组即可,一个分组在此位上为1,另一组在此位上为0;这两个数分别位于这两个分组中;
    // 对两个分组中的数分别计算异或,得到的值即为所求的值; 每个分组中除所求的数外,其余的都出现偶数次; 
    no1 = 0, no2 = 0;  
    for (i = 0; i < n; i++)
    {  
        if (((a[i] >> j) & 1) == 0)  // 分组1
        {
            no1 ^= a[i];  
        }        
        else                        // 分组2
        {  
            no2 ^= a[i];
        }
    }  
} 
如果缺少的两个数字相同
(此时数组中所有ID都是成对出现,异或值还是为0,不能使用异或实现)
方法:可以使用不变量实现。丢失两个,生成两个方程,联立求值
此时我们采取的方法如下:
  1. (1)首先计算出初始未丢失之前,所有ID之和。  
  2. (2)然后计算出丢失之后的ID之和,然后(1)(2)结果进行相减操作,得到方程x+ y = a。  
  3. (3)利用丢失前后平方和之差,来与(2)进行联立,得到方程x * x + y * y = b。  
  4. (4)对两方程进行联立,即可以求出最终的结果。
问题3、已知一个数组,数组丢失了三个数据,我们要把这三个数据找出来
              之后可以扩展到N个
方法一:我们需要建立三/N个方程,求出这些都是的数
此时,当方程为N时,要求N个方程可不好求
方法二:使用计数排序 + 计数值达到A时Map不在存储
这时,最终可以得到这几个数
给你一副杂乱的扑克牌(不包括大小王),任意从其中抽出一张牌,怎样用最简单的方法来知道抽出的是1~13中的那一张?(不要求知道花色)
方法:利用不变量
事先算好所有牌的和(1+...+13) x 4 = 364
然后分别减去留下的牌点数,最终得到的就是抽出的那一张

Also check http://www.xuebuyuan.com/1014709.html

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts