350 Intersection of Two Arrays II两个数组的交集2

题目

尝试

第一次尝试：

class Solution {public int[] intersect(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int[] nums3 = new int[nums1.length + nums2.length];int size = 0;for( int i = 0; i < nums1.length; i++){for ( int j = 0; j < nums2.length; j++){if (nums1[i] == nums2[j]){nums3[j] = nums2[j];nums1[i] = -1;nums2[j] = -1;size++;}}}/*int zero = 0;for (int k = 0; k < nums3.length; k++){if (nums3[k] == 0){zero++;}}int[] nums4 = new int[nums3.length - zero];int n = 0; for ( int m = 0; m < nums3.length; m++){if (nums3[m] != 0){nums4[n] = nums3[m];n++;}}*///return nums4;int[] nums5 = new int[size];for (int x = 0; x < size; x++){nums5[x] = nums3[x];}return nums5;}
}

中间注释掉的是除去0，因为新数组会自动填充0，但是题目里两个数组本身也含有0，所以此法作罢。后面使用的方法是把数组不含后面0部分的转移到新数组（按照size长度，也就是答案长度）。然而出现了下面这个诡异的示例报错：

输入：
[4,9,5]
[9,4,9,8,4]
输出：
[4,0]
预期结果：
[4,9]

因为不知道错在哪里了所以此法作罢。。。

法一，集合

class Solution {public int[] intersect(int[] nums1, int[] nums2) {List<Integer> list1 = new ArrayList<>();for (int num : nums1) {list1.add(num);}List<Integer> list2 = new ArrayList<>();for (int num : nums2) {if (list1.contains(num)) {list2.add(num);// 从 list1 除去已匹配的数值list1.remove(Integer.valueOf(num));}}int[] res = new int[list2.size()];int i = 0;for (int num : list2) {res[i++] = num;}return res;}
}

法二，哈希表

题解
思路：

• 由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

• 首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

• 为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

时间复杂度：O(m+n)O(m+n)，其中 mm 和 nn 分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。

空间复杂度：O(\min(m,n))O(min(m,n))，其中 mm 和 nn 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。

class Solution {public int[] intersect(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {return intersect(nums2, nums1);}Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums1) {int count = map.getOrDefault(num, 0) + 1;map.put(num, count);}int[] intersection = new int[nums1.length];int index = 0;for (int num : nums2) {int count = map.getOrDefault(num, 0);if (count > 0) {intersection[index++] = num;count--;if (count > 0) {map.put(num, count);} else {map.remove(num);}}}return Arrays.copyOfRange(intersection, 0, index);}
}

121 Best Time to Buy and Sell Stock买卖股票的最佳时机

题目

尝试

class Solution {public int maxProfit(int[] prices) {int profit = 0;for (int i = 0;i < prices.length; i++){for (int j = i + 1;j < prices.length;j++){if (prices[j] > prices[i]){profit = Math.max(profit, (prices[j] - prices[i]));}}}return profit;}
}

结果是超出时间限制，200 / 211 个通过测试用例
显然大暴搜不可取。

法一 动规

思路：
前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

法二 贪心

// 动态规划
public class Solution {public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}int[] have = new int[len];  // 表示第i天持有股票所得最多现金int[] no = new int[len];    // 表示第i天不持有股票所得最多现金have[0] = -prices[0]; // 此时的持有股票就一定是买入股票了no[0] = 0;            // 不持有股票那么现金就是0for (int i = 1; i < len; i++) {have[i] = Math.max(have[i-1], -prices[i]);no[i] = Math.max(no[i-1], prices[i] + have[i-1]);}return no[len - 1];}
}// 贪心法
class Solution {public int maxProfit(int[] prices) {int low = Integer.MAX_VALUE;int result = 0;for (int i = 0; i < prices.length; i++) {low = Math.min(low, prices[i]);  // 取最左最小价格result = Math.max(result, prices[i] - low); // 直接取最大区间利润}return result;}
}