Google 新鲜面筋

我觉得第一条是不是应该用动归去做 dp[n][k][2], 分别表示前n个数中k个数的乘积的最大值域做小值。这样时间复杂度是O(nk)的。

hesha0987 发表于 2016-2-26 07:31
priority_queue 的复杂度和sort是一样的吧？都是nlogn。
并且priority_queue的话 需要用一个min heap 和 ...

用pq是nlogk

googlerr 发表于 2016-2-26 11:45
应该是Queue里面只放K个元素，一个里面放最大的K个，另一个里面放最小的K个

这样之后该怎么办呢？把minHeap和maxHeap各自的K个数乘起来比较乘积大小？但是还得考虑一部分数来自minHeap一部分数来自maxHeap的情况啊，感觉很复杂……

Wrath 发表于 2016-3-9 05:44
这样之后该怎么办呢？把minHeap和maxHeap各自的K个数乘起来比较乘积大小？但是还得考虑一部分数来自minHe ...

确实，情况是挺复杂的，先撇开overflow的话，还得考虑有0的情况

第一题:
Brute Force : O(n2)
Sort: O(nlogn)
指针遍历: O(n)
找FirstMax, SecondMax, FirstMin, SecondMin,
求 Math.max(FirstMax* SecondMax, FirstMin * SecondMin)
(数组情况很多, 有可能只有1个负数,多个负数,没有负数 一个负数自然就去Math.max里边的前者了,多个有可能是后者,没有负数也是前者)

Follow Up:
维护两个大小为k的heap,一个是maxheap,一个是misheap,
每次加入的时间复杂度是 O(logk)
遍历一遍,把每个数都加入两个heap, N次
最后时间复杂度是O(nlogk)
(判断的时候情况还很多,比如两个负数相乘为正,所以可以取一堆成对的负数和正数组合)

看了下第一题的follow up上升到K个数的最大值，觉得大家说的两个heap好像挺可行的，试着写了一个，不过最后取pair写得太繁杂了:(

1. <blockquote>import java.util.*;

复制代码

1. import java.util.*;
   
2. 
   
3. public class MultiK {
   
4.     // assume input nums is valid -> nums.length >= k
   
5.     // not consider overflow
   
6.     public static int multiK(int[] nums, int k) {
   
7.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">if (nums.length == k) {</span>

复制代码

不知道这次能发出来不

至今不懂怎么贴代码…打扰各位了orz

1. import java.util.*;
   
2. 
   
3. public class MultiK {
   
4.     // assume input nums is valid -> nums.length >= k
   
5.     // not consider overflow
   
6.     public static int multiK(int[] nums, int k) {
   
7.         if (nums.length == k) {
   
8.             int res = 1;
   
9.             for (int n : nums) {
   
10.                 res *= n;
    
11.             }
    
12.             return res;
    
13.         }
    
14. 
    
15.         // minHeap saves the k biggest numbers
    
16.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
17.         // maxHeap saves the k smallest numbers
    
18.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
    
19.         int max = Integer.MIN_VALUE;
    
20.         for (int n : nums) {
    
21.             max = Math.max(max, n);
    
22.             // maintain minHeap and maxHeap both with k number
    
23.             minHeap.offer(n);
    
24.             if (minHeap.size() > k) {
    
25.                 minHeap.poll();
    
26.             }
    
27.             maxHeap.offer(n);
    
28.             if (maxHeap.size() > k) {
    
29.                 maxHeap.poll();
    
30.             }
    
31.         }
    
32. 
    
33.         int res = 1;
    
34.         // check special cases
    
35.         // if all negatives, and k is odd
    
36.         // result would be negative, choose from biggest k
    
37.         if (max < 0 && k % 2 == 1) {
    
38.             while (!minHeap.isEmpty()) {
    
39.                 res *= minHeap.poll();
    
40.             }
    
41.             return res;
    
42.         }
    
43. 
    
44.         // otherwise the result would be >= 0
    
45.         // convert heaps to sorted list
    
46.         int[] minK = new int[k];
    
47.         int[] maxK = new int[k];
    
48.         for (int i = k - 1; i >= 0; --i) {
    
49.             minK[i] = maxHeap.poll();
    
50.             maxK[i] = minHeap.poll();
    
51.         }
    
52. 
    
53.         int minPos = 0, maxPos = 0;
    
54.         // if k is odd, poll the largest non-negative first
    
55.         if (k % 2 == 1) {
    
56.             --k;
    
57.             res *= maxK[maxPos];
    
58.             ++maxPos;
    
59.         }
    
60.         // now choose k/2 pairs out of heap
    
61.         while (k != 0) {
    
62.             int minPair = minK[minPos] * minK[minPos + 1];
    
63.             int maxPair = maxK[maxPos] * maxK[maxPos + 1];
    
64.             if (maxPair > minPair) {
    
65.                 res *= maxPair;
    
66.                 maxPos += 2;
    
67.             }
    
68.             else {
    
69.                 res *= minPair;
    
70.                 minPos += 2;
    
71.             }
    
72.             k -= 2;
    
73.         }
    
74. 
    
75.         return res;
    
76.     }
    
77. 
    
78.     public static void main(String[] args) {
    
79.         int[] test1 = {-8, -7, -3, -1, 0, 5, 6, 9};
    
80.         int k = 3;
    
81.         System.out.println("test1: " + MultiK.multiK(test1, k));
    
82. 
    
83.         int[] test2 = {-8, -7, -3, -1, 0, 5, 6, 9};
    
84.         k = 2;
    
85.         System.out.println("test2: " + MultiK.multiK(test2, k));
    
86. 
    
87.         int[] test3 = {-8, -7, -3, -1};
    
88.         k = 3;
    
89.         System.out.println("test3: " + MultiK.multiK(test3, k));
    
90. 
    
91.         int[] test4 = {1, 2, 3, 5, 6, 9};
    
92.         k = 4;
    
93.         System.out.println("test4: " + MultiK.multiK(test4, k));
    
94. 
    
95.         int[] test5 = {-8, -7, -3, -1, 0, 5, 6, 9};
    
96.         k = 7;
    
97.         System.out.println("test5: " + MultiK.multiK(test5, k));
    
98.     }
    
99. }

复制代码

googlerr 发表于 2016-2-26 11:45
应该是Queue里面只放K个元素，一个里面放最大的K个，另一个里面放最小的K个

你说的queue是指PriorityQueue吧，就是一个maxHeap, 一个minHeap?

googlerr 发表于 2016-2-26 11:45
应该是Queue里面只放K个元素，一个里面放最大的K个，另一个里面放最小的K个

你说的queue是指PriorityQueue吧，就是一个maxHeap, 一个minHeap?