Facebook Intern 电面一轮 + Onsite一轮

说说我的想法：
Sort the input and then think about the following two cases:
1. k is larger than the length or all elements are negative or positive
Compute the product of the k rightmost elements
2. Otherwise
Two pointers say i and j initially at the beginning and the end respectively. Traverse the sorted array until we find k numbers and during the traversal, we keep track of the largest product met so far. Every step, we compare a[i] * a[i + 1] with a[j] and pick up the larger one and multiply it by the largest product so far. Update the number of elements we choose so far. Here is the code:

1. public long findLeastProduct(int[] nums, int k) {
   
2.         long product = 1;
   
3. 
   
4.         Arrays.sort(nums);
   
5.         //special case when k is larger than the length or all elements are negative or positive
   
6.         if (k >= nums.length || nums[nums.length - 1] <= 0 || nums[0] >= 0) {
   
7.             for (int i = nums.length - 1; i >= Math.max(0, nums.length - k); i--) {
   
8.                 product *= nums[i];
   
9.             }
   
10.         }else {
    
11.             int l = 0, r = nums.length - 1;
    
12.             while (k > 0) {
    
13.                 if (nums[l] * nums[l + 1] > nums[r]) {
    
14.                     product *= nums[l] * nums[l + 1];
    
15.                     l += 2;
    
16.                     k -= 2;
    
17.                 }else {
    
18.                     product *= nums[r--];
    
19.                     k--;
    
20.                 }
    
21.             }
    
22.             if (product < 0) product = product / nums[r + 1] * nums[l] * nums[l + 1];
    
23.         }
    
24.         return product;
    
25.     }
    
26. 
    
27.     @Test
    
28.     public void test() {
    
29.         int[] nums = {-1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -10000};
    
30.         System.out.println(findLeastProduct(nums, 3));
    
31.     }

复制代码

补充内容 (2015-6-26 04:40):
Modify the 22 line:
if (product < 0) product = product / (nums[r + 1] * nums[l]) * nums[l + 1];

晕菜，刚刚查处了bug,对上个帖子做个更正：

1. public long findLeastProduct(int[] nums, int k) {
   
2.         long product = 1;
   
3. 
   
4.         Arrays.sort(nums);
   
5.         //special case when k is larger than the length or all elements are negative or positive
   
6.         if (k >= nums.length || nums[nums.length - 1] <= 0 || nums[0] >= 0) {
   
7.             for (int i = nums.length - 1; i >= Math.max(0, nums.length - k); i--) {
   
8.                 product *= nums[i];
   
9.             }
   
10.         }else {
    
11.             int l = 0, r = nums.length - 1;
    
12.             while (k > 0) {
    
13.                 if (k == 1) {
    
14.                     if (nums[r] >= 0) product *= nums[r];
    
15.                     else product = product / nums[r + 1] * nums[l] * nums[l + 1];
    
16.                     k--;
    
17.                 } else if (nums[l] * nums[l + 1] > nums[r]) {
    
18.                     product *= nums[l] * nums[l + 1];
    
19.                     l += 2;
    
20.                     k -= 2;
    
21.                 }else {
    
22.                     product *= nums[r--];
    
23.                     k--;
    
24.                 }
    
25.             }
    
26.         }
    
27.         return product;
    
28.     }
    
29. 
    
30.     @Test
    
31.     public void test() {
    
32.         int[] nums = {-1, -2, -3, -4, 5, 6, 7};
    
33.         System.out.println(findLeastProduct(nums, 4));
    
34.     }

复制代码

ccgogo123 发表于 2015-6-26 04:53
晕菜，刚刚查处了bug,对上个帖子做个更正：

Exactly，现在回头来看，这题大概就一个普通的算法题，不过还是很巧妙的就是。

这种先排序的思路，都快被各种O(n)的题目给挤压没了。

绝对值排序挺好思考的感觉~排好后取 K 个最大的，如果负数个数是 even，那就完事了；如果是 odd，那么两种方法，减少一个负数，或者增加一个负数，两种情况比较下哪个大就好了。

ccgogo123 发表于 2015-6-26 04:53
晕菜，刚刚查处了bug,对上个帖子做个更正：

有个test case不对，{-7, -7, -2, -1, 0, 0, 9}, 结果应该是98(-7*-7*-2*-1)， 但你的程序结果是0

ccgogo123 发表于 2015-6-26 04:53
晕菜，刚刚查处了bug,对上个帖子做个更正：

这个代码不能解决：-7 ~ -1的case

不用swap用write
这句话猴哥可以详细解释一下吗

JamesJi 发表于 2015-10-23 01:48
不用swap用write
这句话猴哥可以详细解释一下吗

就是直接A[l] = A[r]，A[r]上什么值留下来无所谓了。

xiaoma318 发表于 2015-8-24 07:00
绝对值排序挺好思考的感觉~排好后取 K 个最大的，如果负数个数是 even，那就完事了；如果是 odd，那么两种 ...

我和你想的方法一样

堕落的猴子 发表于 2015-10-23 02:02
就是直接A[l] = A[r]，A[r]上什么值留下来无所谓了。

請問 A[r] 不用覆寫成 0 嗎?