文章目錄

• 前言
• 一、題目描述
• 二、解題
• • 1.使用HashMap，邊存邊加入邊合并
  • 2.使用二維數(shù)組接收輸入，存入HashMap中，排序key后再輸出
• 總結(jié)

---

前言

本題是牛客網(wǎng)華為機(jī)試中的一道題，題目標(biāo)記為簡單，但是我們可以從中學(xué)到一些知識。

---

一、題目描述

數(shù)據(jù)表記錄包含表索引index和數(shù)值value（int范圍的正整數(shù)），請對表索引相同的記錄進(jìn)行合并，即將相同索引的數(shù)值進(jìn)行求和運(yùn)算，輸出按照index值升序進(jìn)行輸出。
提示:
0 <= index <= 11111111
1 <= value <= 100000
輸入描述：
先輸入鍵值對的個數(shù)n（1 <= n <= 500）
接下來n行每行輸入成對的index和value值，以空格隔開
輸出描述：
輸出合并后的鍵值對（多行）
示例一：

輸入： 4 0 1 0 2 1 2 3 4 復(fù)制 輸出： 0 3 1 2 3 4

示例二：

輸入： 3 0 1 0 2 8 9 復(fù)制 輸出： 0 3 8 9

二、解題

1.使用HashMap，邊存邊加入邊合并

采用hash表存放數(shù)據(jù)，每次輸入查詢是否有存在的key，存在就將value累加到表中，最后輸出表。
代碼如下：

public static void main(String[] args) { // 解法一：直接用key，value進(jìn)行接受輸入的值，邊接收邊往map中加入Scanner scanner = new Scanner(System.in);int tableSize = scanner.nextInt();Map<Integer, Integer> table = new HashMap<>(tableSize);for (int i = 0; i < tableSize; i++) {int key = scanner.nextInt();int value = scanner.nextInt();if (table.containsKey(key)) {table.put(key, table.get(key) + value);} else {table.put(key, value);}}for (Integer key : table.keySet()) {System.out.println( key + " " + table.get(key));}}

2.使用二維數(shù)組接收輸入，存入HashMap中，排序key后再輸出

代碼如下：

import java.util.*;public class Main {public static void main(String[] args) {//解法二：創(chuàng)建二維數(shù)組接收輸入的值，然后用mergeTable方法，實際跟解法一是一樣的Scanner sc = new Scanner(System.in);while (sc.hasNext()){int n = sc.nextInt();int[][] table = new int[n][2];for (int i = 0; i < n; i++) {table[i][0] = sc.nextInt();table[i][1] = sc.nextInt();}Main main = new Main();main.mergeTable2(n,table);}sc.close();}/*** 創(chuàng)建map的時候指定大小* @param n* @param table*/public void mergeTable(int n,int[][] table){Map<Integer,Integer> map = new HashMap<>(n);for (int i = 0; i < n; i++) {if (map.containsKey(table[i][0])){map.put(table[i][0],map.get(table[i][0]) + table[i][1]);}else {map.put(table[i][0],table[i][1]);}}for (Integer key : map.keySet()) {System.out.println(key + " " + map.get(key));}} }

以下方法mergeTable2跟解法二中的方法mergeTable有什么區(qū)別能看出來嗎？可以使用文章最后的用例進(jìn)行測試。

/*** @param n* @param table*/public void mergeTable2(int n,int[][] table){Map<Integer,Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {if (map.containsKey(table[i][0])){map.put(table[i][0],map.get(table[i][0]) + table[i][1]);}else {map.put(table[i][0],table[i][1]);}}//keySet():該方法返回map中所有key值的列表Set set = map.keySet();//set.toArray()返回的是Object數(shù)組類型Object[] array = set.toArray();//排序keyArrays.sort(array);//新建newMap存放排序后的mapMap newMap = new HashMap();//map.keySet是獲取map的key值for (Object key : array) {newMap.put(key,map.get(key));System.out.println(key + " " + newMap.get(key));}}

---

總結(jié)

看似是兩種解法，實際上是一種，但是稍微有一點點區(qū)別，仔細(xì)看下，在創(chuàng)建HashMap的時候，一個指定來map的大小（容量），一個未指定，未指定容量的需要根據(jù)map的key進(jìn)行排序，才能得到一個題目要求的輸出（按照index值升序進(jìn)行輸出）。

148 129 85580 116 50881 117 27393 100 32215 6 88835 88 40361 57 78653 28 59528 41 41907 46 88880 53 64598 5 19381 45 27819 143 370 103 75359 10 8701 43 32347 3 84515 134 11988 65 89941 138 60355 65 16308 120 857 98 62578 22 62628 40 24666 118 23155 0 11817 13 36474 10 55782 4 77316 91 19024 80 72421 28 36353 8 88937 36 26142 51 46105 116 12428 109 31227 36 88168 135 58543 94 42200 112 54610 66 59272 0 41231 90 88635 147 40695 56 4994 64 62797 129 92991 83 5694 132 30492 115 69553 58 70010 34 66064 113 6516 111 69569 56 30166 131 38872 10 14671 24 3464 113 18983 77 15226 85 74879 126 53743 112 30751 49 11189 4 19369 35 74225 35 45722 94 51260 125 67595 56 17781 147 89199 9 91999 57 2594 15 42814 146 75003 60 79814 115 27794 105 20071 8 72038 112 7831 50 90288 27 80166 30 58519 120 33213 94 21512 22 77163 89 20689 106 7601 83 43666 90 20490 6 18760 115 39610 132 57359 133 22082 55 86957 128 56323 121 84561 121 33028 52 50357 55 65649 17 55645 104 87925 135 80568 105 68936 126 64270 101 12090 58 45644 31 62144 71 91373 90 65686 22 33562 102 81895 68 60578 97 26097 13 22247 26 4823 83 23024 44 72254 44 59718 90 81011 41 21065 118 4218 41 78235 63 4698 141 29922 106 222 95 58962 70 28187 116 34961 120 52587 108 74238 84 1943 138 46424 68 64937 109 52784 130 27464 121 29581 140 46817 103 46954 7 69852 18 68899 10 82159 68 10725 64 45113 91 64159

總結(jié)

以上是生活随笔為你收集整理的【牛客刷题HJ8】合并表记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。