网站空间不续费,百度竞价推广是什么,慈利网站开发,网站ico设计题目
两个有序数组#xff0c;第一个有序数组m是1000w个元素#xff0c;第二个有序数组n是1000个元素#xff0c;求交集#xff0c;需要考虑时间复杂度和空间复杂度。
解题思路
解法1#xff1a;遍历小数组n#xff0c;在m数组中进行折半查找#xff0c;根据数组有序…题目
两个有序数组第一个有序数组m是1000w个元素第二个有序数组n是1000个元素求交集需要考虑时间复杂度和空间复杂度。
解题思路
解法1遍历小数组n在m数组中进行折半查找根据数组有序的特性每次折半找到数据以后下次直接再折半就是另外一半数据了所以时间复杂度是O(nlgm) 解法2双指针同时遍历两个数组不相等小的那个数前进一步相等都前进一步时间复杂度是O(m)
代码参考
这里采用折半查找
public static void main(String[] args) {int[] m new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};int[] n new int[]{2, 5};ListInteger results Lists.newArrayList();int left 0;int right m.length - 1;for (int i 0; i n.length; i) {while (left right) {int mid (right left) / 2;if (n[i] m[mid]) {results.add(n[i]);left mid;right m.length - 1;break;}if (n[i] m[mid]) {left mid;}if (n[i] m[mid]) {right mid;}}}System.out.println(results);}思维拓展
遇到有序的数组解题思路一般会用到折半和双指针的思想。 比如[10,9,8,6,5,4,11,12,23] 这种两边大中间小的数据如何排序思路就是用双指针从左右遍历每次取一个最大的数。
