兩個(gè)數(shù)組的交集 II

給定兩個(gè)數(shù)組,編寫一個(gè)函數(shù)來計(jì)算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]

示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]

說明:

  • 輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)死相,應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。
  • 我們可以不考慮輸出結(jié)果的順序囤躁。

****進(jìn)階:****

  • 如果給定的數(shù)組已經(jīng)排好序呢常潮?你將如何優(yōu)化你的算法?
  • 如果 _nums1 _的大小比 _nums2 _小很多揖盘,哪種方法更優(yōu)眉厨?
  • 如果 _nums2 _的元素存儲(chǔ)在磁盤上,磁盤內(nèi)存是有限的兽狭,并且你不能一次加載所有的元素到內(nèi)存中憾股,你該怎么辦鹿蜀?

我自己想的算法,不依賴JDK現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)服球,僅使用簡(jiǎn)單的數(shù)組結(jié)構(gòu)茴恰、while、for等循環(huán)

public static int[] intersect(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        if (len1 == 0 || len2 == 0) {
            int[] aa = {};
            return aa;
        }

        int notSameIndex = 0;
        int tempSwapNum = 0;
        int tempSameNum = 0;
        int tempLesserTimes = 0;

        // 是否出現(xiàn)過交集斩熊,一開始為false
        boolean isIntersect = false;

        if (len1 >= len2) {
            for (int i = 0; i < nums2.length; i++) {
                for (int j = 0; j < nums1.length; j++) {
                    // 相等往枣,而且要沒有判斷過的
                    if (nums2[i] == nums1[j] && isNotExist(isIntersect, notSameIndex - 1, nums2[i], nums2)) {
                        // 如果有交集,那么需要找出此元素在nums1,nums2中出現(xiàn)的次數(shù)粉渠,返回較小的值
                        tempSameNum = nums2[i];
                        tempLesserTimes = getLesserTimes(tempSameNum, nums1, nums2);
                        // 對(duì)nums2的元素進(jìn)行交換位置分冈,把交集部分移動(dòng)到數(shù)組前面
                        for (int i2 = notSameIndex; i2 < nums2.length; i2++) {
                            if (tempLesserTimes > 0 && tempSameNum == nums2[i2]) {
                                tempSwapNum = nums2[notSameIndex];
                                nums2[notSameIndex] = tempSameNum;
                                nums2[i2] = tempSwapNum;
                                notSameIndex++;
                                tempLesserTimes--;
                            }
                        }

                        isIntersect = true;
                    }
                }
            }
            return Arrays.copyOf(nums2, notSameIndex);
        } else {
            for (int i = 0; i < nums1.length; i++) {
                for (int j = 0; j < nums2.length; j++) {
                    // 相等,而且要沒有判斷過的
                    if (nums1[i] == nums2[j] && isNotExist(isIntersect, notSameIndex - 1, nums1[i], nums1)) {
                        // 如果有交集霸株,那么需要找出此元素在nums1,nums2中出現(xiàn)的次數(shù)雕沉,返回較小的值
                        tempSameNum = nums1[i];
                        tempLesserTimes = getLesserTimes(tempSameNum, nums1, nums2);
                        // 對(duì)nums2的元素進(jìn)行交換位置,把交集部分移動(dòng)到數(shù)組前面
                        for (int i2 = notSameIndex; i2 < nums1.length; i2++) {
                            if (tempLesserTimes > 0 && tempSameNum == nums1[i2]) {
                                tempSwapNum = nums1[notSameIndex];
                                nums1[notSameIndex] = tempSameNum;
                                nums1[i2] = tempSwapNum;
                                notSameIndex++;
                                tempLesserTimes--;
                            }
                        }

                        isIntersect = true;
                    }
                }
            }
            return Arrays.copyOf(nums1, notSameIndex);
        }
    }

    private static boolean isNotExist(boolean isIntersect, int range, int num, int[] nums) {
        if (isIntersect) {
            boolean ret = true;
            for (int i = 0; i < nums.length; i++) {
                if (i <= range && nums[i] == num) {
                    ret = false;
                    break;
                }
            }
            return ret;
        } else {
            return !isIntersect;
        }
    }

    private static int getLesserTimes(int num, int[] nums1, int[] nums2) {
        int times1 = 0;
        for (int i = 0; i < nums1.length; i++) {
            if (num == nums1[i]) {
                times1++;
            }
        }

        int times2 = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (num == nums2[i]) {
                times2++;
            }
        }
        return Math.min(times1, times2);
    }

下面這種算法是先對(duì)已知的兩個(gè)數(shù)組進(jìn)行排序去件,

public static int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        List<Integer> list = new ArrayList<>();
        for (int i = 0, j = 0; i < nums1.length && j < nums2.length;) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

下面這種算法是使用 jdk現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)坡椒,java.util.Map

    public static int[] intersect3(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map1 = new HashMap<>();
        for (Integer num : nums1)
            if (map1.containsKey(num))
                map1.replace(num, map1.get(num) + 1);
            else
                map1.put(num, 1);

        ArrayList<Integer> intersection = new ArrayList<>(16);
        for (Integer num : nums2) {
            if (map1.containsKey(num) && map1.get(num) > 0) {
                intersection.add(num);
                map1.replace(num, map1.get(num) - 1);
            }
        }

        int[] ret = new int[intersection.size()];
        for (int i = 0; i < intersection.size(); i++) {
            ret[i] = intersection.get(i);
        }

        return ret;
    }
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市箫攀,隨后出現(xiàn)的幾起案子肠牲,更是在濱河造成了極大的恐慌,老刑警劉巖靴跛,帶你破解...
    沈念sama閱讀 218,755評(píng)論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異渡嚣,居然都是意外死亡梢睛,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,305評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門识椰,熙熙樓的掌柜王于貴愁眉苦臉地迎上來绝葡,“玉大人,你說我怎么就攤上這事腹鹉〔爻” “怎么了?”我有些...
    開封第一講書人閱讀 165,138評(píng)論 0 355
  • 文/不壞的土叔 我叫張陵功咒,是天一觀的道長(zhǎng)愉阎。 經(jīng)常有香客問我,道長(zhǎng)力奋,這世上最難降的妖魔是什么榜旦? 我笑而不...
    開封第一講書人閱讀 58,791評(píng)論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮景殷,結(jié)果婚禮上溅呢,老公的妹妹穿的比我還像新娘澡屡。我一直安慰自己,他們只是感情好咐旧,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,794評(píng)論 6 392
  • 文/花漫 我一把揭開白布驶鹉。 她就那樣靜靜地躺著,像睡著了一般铣墨。 火紅的嫁衣襯著肌膚如雪梁厉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,631評(píng)論 1 305
  • 那天踏兜,我揣著相機(jī)與錄音词顾,去河邊找鬼。 笑死碱妆,一個(gè)胖子當(dāng)著我的面吹牛肉盹,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播疹尾,決...
    沈念sama閱讀 40,362評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼上忍,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了纳本?” 一聲冷哼從身側(cè)響起窍蓝,我...
    開封第一講書人閱讀 39,264評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎繁成,沒想到半個(gè)月后吓笙,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,724評(píng)論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡巾腕,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,900評(píng)論 3 336
  • 正文 我和宋清朗相戀三年面睛,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片尊搬。...
    茶點(diǎn)故事閱讀 40,040評(píng)論 1 350
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡叁鉴,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出佛寿,到底是詐尸還是另有隱情幌墓,我是刑警寧澤,帶...
    沈念sama閱讀 35,742評(píng)論 5 346
  • 正文 年R本政府宣布冀泻,位于F島的核電站常侣,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏腔长。R本人自食惡果不足惜袭祟,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,364評(píng)論 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望捞附。 院中可真熱鬧巾乳,春花似錦您没、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,944評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至压状,卻和暖如春仆抵,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背种冬。 一陣腳步聲響...
    開封第一講書人閱讀 33,060評(píng)論 1 270
  • 我被黑心中介騙來泰國打工镣丑, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人娱两。 一個(gè)月前我還...
    沈念sama閱讀 48,247評(píng)論 3 371
  • 正文 我出身青樓莺匠,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國和親十兢。 傳聞我的和親對(duì)象是個(gè)殘疾皇子趣竣,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,979評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容