map<int,int>和数组有什么区别

Question

LeetCode82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        map<int,int>nums;
        ListNode *p = head;
        ListNode *new_head = new ListNode(0,head);
       
        ListNode *pre =  new_head;
        ListNode *temp = new_head;
        //new_head->next =head;
        while(p)
        {
            nums[p->val]++;
            p = p->next; 
        }
        pre = pre->next;
        while(pre){
            if(nums[pre->val] > 1){
                temp->next= NULL;
                pre =pre->next;
            }
            else {
             temp->next =pre;
             temp = temp -> next;
             pre = pre->next;
            }
            
        }
        
        if(temp == new_head) return NULL;
        return new_head->next;
        
    }
};

我用的是map定义了nums，但是如果我用vector 数组，答案确是错的（就是报错），而map<int,int>不就相当于数组吗

Answer 1

map<int,int>是数值对，相当于一个具有两个整型变量的结构体。一个代表具体的数值，一个代表该数值出现的次数。但vector只是一个值得数组。不太一样。如果用vector，有两种办法，一是定义元素是vector的vector，每个vector元素包含两个数值，就类似于map了。另一种是vector相邻两个数值分别表示具体数值和出现次数，也可以解决这个题目。