LintCode547/548_求数组交集不同解法小结

gxyz 发布于2019-08-16 10:34 / 636人阅读

摘要：求数组交集不同解法小结声明文章均为本人技术笔记，转载请注明出处求数组交集要求元素不重复，给出两个数组，求二者交集且元素不重复，查找会超时解法一排序二分查找算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用保存实现去重解法

LintCode547/548_求数组交集不同解法小结

[TOC]

声明

文章均为本人技术笔记，转载请注明出处：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

LintCode547：求数组交集_要求元素不重复

LintCode547，给出两个数组，求二者交集且元素不重复，$O(N^{2})$查找会超时；

解法一：排序+二分查找

$O(N ^{2})$算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用HashSet保存实现去重；

/**
 * 解法1：排序+二分+HashSet去重
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays/
 * 求数组交集，要求元素不重复出现
 * @author yzwall
 */
class Solution {
    public int[] intersection(int[] num1, int[] num2) {
        int[] results;
        if (num1 == null || num1.length == 0 || num2 == null || num2.length == 0) {
            results = new int[0];
            return results;
        }
        
        HashSet set = new HashSet<>();
        Arrays.sort(num1);
        Arrays.sort(num2);
        int index2 = 0;
        for (int i = 0; i < num1.length; i++) {
            // num2是子集
            if (index2 > num2.length - 1) {
                break;
            }
            int index = binarySearch(num2, index2, num1[i]);
            if (index != -1) {
                // set去重
                set.add(num1[i]);
                // num2指针移动
                index2 = index;
            }
        }
        
        results = new int[set.size()];
        int i = 0;
        for (Integer cur : set) {
            results[i++] = cur.intValue();
        }
        return results;
    }
    
    // Index2~num.length - 1，经典二分查找
    private int binarySearch(int[] num, int index2, int target) {
        int start = index2;
        int end = num.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (num[mid] == target) {
                return mid;
            } else if (num[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (num[start] == target) {
            return start;
        }
        if (num[end] == target) {
            return end;
        }
        return -1;
    }
}

解法二：HasSet暴力去重

直接运用两个HashSet实现去重求交集，与解法一相比实现简单；

/**
 * 解法2：HashSet暴力去重
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays/
 * 求数组交集，要求元素不重复出现
 * @author yzwall
 */
class Solution {
    public int[] intersection(int[] num1, int[] num2) {
        int[] results;
        if (num1 == null || num1.length == 0 || num2 == null || num2.length == 0) {
            results = new int[0];
            return results;
        }
        HashSet hash1 = new HashSet<>();
        for (int i = 0; i < num1.length; i++) {
            hash1.add(num1[i]);
        }
        HashSet hash2 = new HashSet<>();
        for (int i = 0; i < num2.length; i++) {
            if (hash1.contains(num2[i])) {
                hash2.add(num2[i]);
            }
        }
        
        results = new int[hash2.size()];
        int i = 0;
        for (Integer num : hash2) {
            results[i++] = num;
        }
        
        return results;
    }
}

解法三：双指针法（重视）

通过双指针求交集，必须首先将求交集的两数组排序；

/**
 * 解法3：双指针法
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays/
 * 求数组交集，要求元素不重复出现
 * @author yzwall
 */
class Solution {
    public int[] intersection(int[] num1, int[] num2) {
        int[] results;
        if (num1 == null || num1.length == 0 || num2 == null || num2.length == 0) {
            results = new int[0];
            return results;
        }
        Arrays.sort(num1);
        Arrays.sort(num2);
        int i = 0, j = 0;
        int index = 0;
        int[] temp = new int[num1.length];
        while (i < num1.length && j < num2.length) {
            if (num1[i] == num2[j]) {
                // temp[index - 1] != num1[i]去重
                if (index == 0 || temp[index - 1] != num1[i]) {
                    temp[index++] = num1[i];
                }
                i++;
                j++;
            } else if (num1[i] < num2[j]) {
                i++;
            } else {
                j++;
            }
        }
        
        i = 0;
        results = new int[index];
        for (i = 0; i < index; i++) {
            results[i] = temp[i];
        }
        return results;
    }
}

LintCode548：求数组交集变种

在求数组交集的基础上，要求交集元素出现次数与在数组中出现次数相同；

解法一：HashMap统计次数实现

通过HashMap记录数组中每个元素与对应的出现次数；

/**
 * 解法2：HashMap统计重复出现次数
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays-ii/
 * 求两数组交集，要求交集元素按照最小出现次数出现
 * @author yzwall
 */
class Solution {
    public int[] intersection(int[] num1, int[] num2) {
        int[] results;
        if (num1 == null || num1.length == 0 || num2 == null || num2.length == 0) {
            results = new int[0];
            return results;
        }
        
        HashMap hash = new HashMap<>();
        for (int i = 0; i < num1.length; i++) {
            if (hash.containsKey(num1[i])) {
                hash.put(num1[i], hash.get(num1[i]) + 1);
            } else {
                hash.put(num1[i], 1);
            }
        }
        
        ArrayList list = new ArrayList<>();
        for (int i = 0; i < num2.length; i++) {
            if (hash.containsKey(num2[i]) && hash.get(num2[i]) > 0) {
                list.add(num2[i]);
                hash.put(num2[i], hash.get(num2[i]) - 1);
            }
        }
        
        results = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            results[i] = list.get(i);
        }
        return results;
    }
}

解法二：排序+二分查找变种+双指针

变种二分查找：与经典二分不同，解法二中二分查找用于找到查找目标第一次出现位置；
双指针解法：经过排序后，假设两数组中拥有某个交集元素cur, 通过二分查找到cur在第二个数组中的位置index,通过双指针cnt1与cnt2统计交集元素cur在两个数组中各自出现的总次数，较小者表示该交集元素在交集中出现的次数；

/**
 * 解法1：排序+二分查找+双指针
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays-ii/
 * 求两数组交集，要求交集元素按照最小出现次数出现
 * @author yzwall
 */
class Solution3 {
    public int[] intersection(int[] num1, int[] num2) {
        int[] results;
        if (num1 == null || num1.length == 0 || num2 == null || num2.length == 0) {
            results = new int[0];
            return results;
        }
        
        ArrayList list = new ArrayList<>();
        Arrays.sort(num1);
        Arrays.sort(num2);
        int index2 = 0;
        int i = 0;
        while(i < num1.length) {
            // num2是子集
            if (index2 > num2.length - 1) {
                break;
            }
            int cnt1 = 1, cnt2 = 1;
            int cur = num1[i];
            int index = binarySearch(num2, index2, cur);
            if (index != -1) {
                // 查找交集元素cur在数组num1中出现总次数
                for (int k = 1; k < num1.length && i + k < num1.length; k++) {
                    if (num1[i + k] != cur) {
                        break;
                    }
                    cnt1++;
                }
                // 查找交集元素cur在数组num2中出现总次数
                for (int k = 1; k < num2.length && index + k < num2.length; k++) {
                    if (num2[index + k] != cur) {
                        break;
                    }
                    cnt2++;
                }
                int min = Math.min(cnt1, cnt2);
                for (int k = 0; k < min; k++) {
                    list.add(cur);
                }
                // num2指针移动
                index2 += cnt2;
            }
            // num1指针移动
            i += cnt1;
        }
        
        results = new int[list.size()];
        i = 0;
        for (Integer cur : list) {
            results[i++] = cur.intValue();
        }
        return results;
    }
    
    // 返回target第一次出现位置，target不存在返回-1
    private int binarySearch(int[] num, int index2, int target) {
        int start = index2;
        int end = num.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (num[mid] == target) {
                end = mid;
            } else if (num[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (num[start] == target) {
            return start;
        }
        if (num[end] == target) {
            return end;
        }
        return -1;
    }
}

GPU云服务器云服务器 python中求交集交集数组 LintCode134_LRU java数组知识小结

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70036.html

两数之和问题各变种多解法小结

摘要：两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处两数之和等于题目大意给出未排序数组和指定目标，返回数组中两数之和的组合元素下标要求下标从开始，而且，保证题目中有且只有个可行解解法暴力时间复杂度求解解题思路暴力二重循环求解两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwal...

lentoo 2019-08-16 10:34 评论0 收藏0
表达式类算法题小结

摘要：将表达式转换为逆波兰式，然后求值转换中缀表达式为逆波兰式鲁棒性检测，表达式中没有操作数计算逆波兰式值参考表达式类算法题小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/ 表达式分类根据运算符与相关操作操作数的位置不同，将表达式分为前缀，中缀和后缀表...

Heier 2019-08-16 10:32 评论0 收藏0
TypeScript实现数组相关简单算法

摘要：本文只是简单理解算法，并不会深入的讨论。大部分来自数组部分。如果数组中每个元素都不相同，则返回。示例输入输出加给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。尽量减少操作次数。算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰...

cloud 2019-08-23 11:55 评论0 收藏0
求数组差/交集函数-php数组函数（二）

摘要：求数组差集函数函数只检查了多维数组中的一维。自定义函数必须返回一个小于零，等于零，或大于零的整数。用自定义函数比较的值，函数参数为数组的值。求数组差集函数函数只检查了多维数组中的一维。可以用 array_diff($array1[0], $array2[0]) 检查更深的维度。 u：自定义函数比较，a(association)：同时比较键和值。自定义函数callable $v...

ChristmasBoy 2019-07-01 10:24 评论0 收藏0