传说中的华为面试题(8分钟写出代码) - Tour大咸鱼 - 博客园



传说中的华为面试题(8分钟写出代码) - Tour大咸鱼 - 博客园

这个题目是在网上看到了,题目描述如下:有两个数组a,b,大小都为n,数组元素的值任意,无序。要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小。不知道是否真的出自华为,但题目难度很大,以我的水平8分钟确实无法写出完整的代码,查阅网上的牛人的思路,理解整理如下:

  1. 对两个数字值进行累加,设差值 A = sum(a) - sum(b)
  2. a的第i个元素和b的第j个元素交换后,a和b的和之差为:A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i]) = sum(a) - sum(b) - 2 (a[i] - b[j]) = A - 2 (a[i] - b[j])
  3. 设x = a[i] - b[j],带入上式得,|A| - |A'| = |A| - |A-2x|
  4. 假设A > 0,当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,如果找不到在(0,A)之间的x,则当前的a和b就是答案。

  算法描述为:将a、b两个数组看出天平两端,各自寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。根据算法描述实现代码:


Read full article from 传说中的华为面试题(8分钟写出代码) - Tour大咸鱼 - 博客园


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts