321. Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

一刷
題解:
一種很簡單的思路,分別從左邊取出[0-k]個元素溉知,從右邊取出[k-0]個元素晋柱,組成長度為k的新array,并比較選擇其中一個最大的。

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        int m = nums2.length;
        int[] ans = new int[k];
        for (int i = Math.max(0, k - m); i <= k && i <= n; ++i) {
            int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if (greater(candidate, 0, ans, 0)) ans = candidate;
        }
        return ans;
    }

    private int[] merge(int[] nums1, int[] nums2, int k) {
        int[] ans = new int[k];
        for (int i = 0, j = 0, r = 0; r < k; ++r)
            ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        return ans;
    }


    public boolean greater(int[] nums1, int i, int[] nums2, int j) {
        while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
    }


//從array中取出k個最大的元素轻局,并保留原來的順序
    public int[] maxArray(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[k];
        for (int i = 0, j = 0; i < n; ++i) {
            while (n - i + j > k && j > 0 && ans[j - 1] < nums[i]) j--;
            if (j < k) ans[j++] = nums[i];
        }
        return ans;
    }
}
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末梧却,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子民珍,更是在濱河造成了極大的恐慌襟士,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件嚷量,死亡現(xiàn)場離奇詭異陋桂,居然都是意外死亡,警方通過查閱死者的電腦和手機津肛,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進店門章喉,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人身坐,你說我怎么就攤上這事秸脱。” “怎么了部蛇?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵摊唇,是天一觀的道長。 經(jīng)常有香客問我涯鲁,道長巷查,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任抹腿,我火速辦了婚禮岛请,結果婚禮上,老公的妹妹穿的比我還像新娘警绩。我一直安慰自己崇败,他們只是感情好,可當我...
    茶點故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布肩祥。 她就那樣靜靜地躺著后室,像睡著了一般。 火紅的嫁衣襯著肌膚如雪混狠。 梳的紋絲不亂的頭發(fā)上岸霹,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天,我揣著相機與錄音将饺,去河邊找鬼贡避。 笑死痛黎,一個胖子當著我的面吹牛,可吹牛的內容都是我干的贸桶。 我是一名探鬼主播舅逸,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼皇筛!你這毒婦竟也來了琉历?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤水醋,失蹤者是張志新(化名)和其女友劉穎旗笔,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拄踪,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡蝇恶,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了惶桐。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片撮弧。...
    茶點故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖姚糊,靈堂內的尸體忽然破棺而出贿衍,到底是詐尸還是另有隱情,我是刑警寧澤救恨,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布贸辈,位于F島的核電站,受9級特大地震影響肠槽,放射性物質發(fā)生泄漏擎淤。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一秸仙、第九天 我趴在偏房一處隱蔽的房頂上張望嘴拢。 院中可真熱鬧,春花似錦寂纪、人聲如沸席吴。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽抢腐。三九已至姑曙,卻和暖如春襟交,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背伤靠。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工捣域, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留啼染,地道東北人。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓焕梅,卻偏偏與公主長得像迹鹅,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子贞言,可洞房花燭夜當晚...
    茶點故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內容