LintCode547/548_求數(shù)組交集不同解法小結(jié)

gxyz 發(fā)布于2019-08-16 10:34 / 681人閱讀

摘要：求數(shù)組交集不同解法小結(jié)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處求數(shù)組交集要求元素不重復(fù)，給出兩個(gè)數(shù)組，求二者交集且元素不重復(fù)，查找會(huì)超時(shí)解法一排序二分查找算法超時(shí)主要發(fā)生在大數(shù)組查找過程，因此采用二分查找提升查找效率，交集用保存實(shí)現(xiàn)去重解法

LintCode547/548_求數(shù)組交集不同解法小結(jié)

[TOC]

聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

LintCode547：求數(shù)組交集_要求元素不重復(fù)

LintCode547，給出兩個(gè)數(shù)組，求二者交集且元素不重復(fù)，$O(N^{2})$查找會(huì)超時(shí)；

解法一：排序+二分查找

$O(N ^{2})$算法超時(shí)主要發(fā)生在大數(shù)組查找過程，因此采用二分查找提升查找效率，交集用HashSet保存實(shí)現(xiàn)去重；

/**
 * 解法1：排序+二分+HashSet去重
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays/
 * 求數(shù)組交集，要求元素不重復(fù)出現(xiàn)
 * @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指針移動(dòng)
                index2 = index;
            }
        }
        
        results = new int[set.size()];
        int i = 0;
        for (Integer cur : set) {
            results[i++] = cur.intValue();
        }
        return results;
    }
    
    // Index2~num.length - 1，經(jīng)典二分查找
    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暴力去重

直接運(yùn)用兩個(gè)HashSet實(shí)現(xiàn)去重求交集，與解法一相比實(shí)現(xiàn)簡(jiǎn)單；

/**
 * 解法2：HashSet暴力去重
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays/
 * 求數(shù)組交集，要求元素不重復(fù)出現(xiàn)
 * @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;
    }
}

解法三：雙指針法（重視）

通過雙指針求交集，必須首先將求交集的兩數(shù)組排序；

/**
 * 解法3：雙指針法
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays/
 * 求數(shù)組交集，要求元素不重復(fù)出現(xiàn)
 * @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：求數(shù)組交集變種

在求數(shù)組交集的基礎(chǔ)上，要求交集元素出現(xiàn)次數(shù)與在數(shù)組中出現(xiàn)次數(shù)相同；

解法一：HashMap統(tǒng)計(jì)次數(shù)實(shí)現(xiàn)

通過HashMap記錄數(shù)組中每個(gè)元素與對(duì)應(yīng)的出現(xiàn)次數(shù)；

/**
 * 解法2：HashMap統(tǒng)計(jì)重復(fù)出現(xiàn)次數(shù)
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays-ii/
 * 求兩數(shù)組交集，要求交集元素按照最小出現(xiàn)次數(shù)出現(xiàn)
 * @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;
    }
}

解法二：排序+二分查找變種+雙指針

變種二分查找：與經(jīng)典二分不同，解法二中二分查找用于找到查找目標(biāo)第一次出現(xiàn)位置；
雙指針解法：經(jīng)過排序后，假設(shè)兩數(shù)組中擁有某個(gè)交集元素cur, 通過二分查找到cur在第二個(gè)數(shù)組中的位置index,通過雙指針cnt1與cnt2統(tǒng)計(jì)交集元素cur在兩個(gè)數(shù)組中各自出現(xiàn)的總次數(shù)，較小者表示該交集元素在交集中出現(xiàn)的次數(shù)；

/**
 * 解法1：排序+二分查找+雙指針
 * http://www.lintcode.com/zh-cn/problem/intersection-of-two-arrays-ii/
 * 求兩數(shù)組交集，要求交集元素按照最小出現(xiàn)次數(shù)出現(xiàn)
 * @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在數(shù)組num1中出現(xiàn)總次數(shù)
                for (int k = 1; k < num1.length && i + k < num1.length; k++) {
                    if (num1[i + k] != cur) {
                        break;
                    }
                    cnt1++;
                }
                // 查找交集元素cur在數(shù)組num2中出現(xiàn)總次數(shù)
                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指針移動(dòng)
                index2 += cnt2;
            }
            // num1指針移動(dòng)
            i += cnt1;
        }
        
        results = new int[list.size()];
        i = 0;
        for (Integer cur : list) {
            results[i++] = cur.intValue();
        }
        return results;
    }
    
    // 返回target第一次出現(xiàn)位置，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云服務(wù)器云服務(wù)器 python中求交集交集數(shù)組 LintCode134_LRU java數(shù)組知識(shí)小結(jié)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70036.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

gxyz

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

C語言進(jìn)階：程序預(yù)處理

閱讀 1852·2021-10-09 09:44
如何控制云主機(jī)-該怎么選擇合適自己的云虛擬主機(jī)？

閱讀 2723·2021-09-22 15:38
【C語言進(jìn)階】C語言實(shí)現(xiàn)通訊錄升級(jí)版 { 含動(dòng)態(tài)擴(kuò)容/銷毀/信息保存功能 }（強(qiáng)烈建議收藏食用）

閱讀 2529·2021-09-09 09:33
iNeuOS工業(yè)互聯(lián)平臺(tái)，增加OPC UA驅(qū)動(dòng)，同步和訂閱方式讀取數(shù)據(jù)

閱讀 734·2021-09-07 09:58
題目：基于Java畢設(shè)項(xiàng)目“e博士”高考志愿輔助填報(bào)系統(tǒng)

閱讀 1847·2021-09-02 15:41
css居中總結(jié)

閱讀 2568·2019-08-30 15:55
畢業(yè)后的第一次總結(jié)。

閱讀 1821·2019-08-30 15:55
HTML 分享頁面到QQ/微信、微博等平臺(tái)

閱讀 578·2019-08-30 15:44

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

LintCode547/548_求數(shù)組交集不同解法小結(jié)

相關(guān)文章

兩數(shù)之和問題各變種多解法小結(jié)

表達(dá)式類算法題小結(jié)

**TypeScript實(shí)現(xiàn)數(shù)組相關(guān)簡(jiǎn)單算法**

**求數(shù)組差/交集函數(shù)-php數(shù)組函數(shù)（二）**

發(fā)表評(píng)論

0條評(píng)論

gxyz

男|高級(jí)講師

TA的文章

C語言進(jìn)階：程序預(yù)處理

如何控制云主機(jī)-該怎么選擇合適自己的云虛擬主機(jī)？

【C語言進(jìn)階】C語言實(shí)現(xiàn)通訊錄升級(jí)版 { 含動(dòng)態(tài)擴(kuò)容/銷毀/信息保存功能 }（強(qiáng)烈建議收藏食用）

iNeuOS工業(yè)互聯(lián)平臺(tái)，增加OPC UA驅(qū)動(dòng)，同步和訂閱方式讀取數(shù)據(jù)

題目：基于Java畢設(shè)項(xiàng)目“e博士”高考志愿輔助填報(bào)系統(tǒng)

css居中總結(jié)

畢業(yè)后的第一次總結(jié)。

HTML 分享頁面到QQ/微信、微博等平臺(tái)

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

LintCode547/548_求數(shù)組交集不同解法小結(jié)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！