方法一：散列表
题目要求“时间复杂度尽可能高效”，所以可以考虑用散列表进行辅助。
算法基本思想如下：
从链表第一个元素开始遍历链表：
如果散列表中没有绝对值为当前元素绝对值的记录，保留该结点，并在散列表中记录当前元素绝对值，继续检查下一个结点。
如果散列表中已经有绝对值为当前元素绝对值的记录，删除该结点，继续检查下一个结点。
直到链表遍历结束。
C代码如下（含测试用例）：
C语言没有散列表这种数据结构，可以考虑用数组代替，由题目条件 |data|≤n ，只需要开辟一个大小为 n+1 的辅助数组。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ListNode {
int data;
struct ListNode* link;
};
struct ListNode* deleteDuplicates(struct ListNode* head, int n) {
int st[n + 1];
memset(st, 0, sizeof(st));
struct ListNode *prev = head;
struct ListNode *curr = head->link;
while (curr != NULL) {
if (st[abs(curr->data)] == 1) {
prev->link = curr->link;
struct ListNode *temp = curr;
curr = curr->link;
free(temp);
} else {
st[abs(curr->data)] = 1;
prev = prev->link;
curr = curr->link;
}
}
return head;
}
struct ListNode* createLinkedList(int *a, int n) {
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
for (int i = 0; i < n; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = a[i];
node->link = NULL;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
int a[] = {21, -15, -15, -7, 15};
struct ListNode* head = createLinkedList(a, 5);
struct ListNode* newhead = deleteDuplicates(head, 32);
struct ListNode* curr = head->link;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->link;
}
return 0;
}
复杂度分析
- 时间复杂度： O(m+n) ，初始化辅助数组时间为 O(n) ，只需要遍历一次链表，时间为 O(m) 。
- 空间复杂度： O(n) ，辅助数组空间为 O(n) 。
C++代码如下（含测试用例）：
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int data;
ListNode *link;
};
ListNode* deleteDuplicates(ListNode* head, int n) {
vector<int>st(n + 1);
ListNode *prev = head;
ListNode *curr = head->link;
while (curr) {
if (st[abs(curr->data)]) {
prev->link = curr->link;
ListNode *temp = curr;
curr = curr->link;
delete temp;
} else {
st[abs(curr->data)] = 1;
prev = prev->link;
curr = curr->link;
}
}
return head;
}
ListNode* createLinkedList(vector<int> nums) {
ListNode* head = new ListNode();
ListNode* tail = head;
for (int i = 0; i < nums.size(); i++) {
ListNode* node = new ListNode();
node->data = nums[i];
node->link = nullptr;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
vector<int>nums{21, -15, -15, -15, -7, 15, 15};
ListNode* head = createLinkedList(nums);
ListNode* newhead = deleteDuplicates(head, 32);
ListNode* curr = newhead->link;
cout << "head";
while (curr) {
cout << "->" << curr->data;
curr = curr->link;
}
return 0;
}
复杂度分析
- 时间复杂度： O(m+n) ，初始化辅助数组时间为 O(n) ，只需要遍历一次链表，时间为 O(m) 。
- 空间复杂度： O(n) ，辅助数组空间为 O(n) 。
虽然C++的标准函数库提供了具有散列表功能的数据结构如unordered_set和unordered_map，但首选仍然是用数组代替散列表，unordered_set和unordered_map不到迫不得已的情况不考虑使用，散列表适用于元素稀疏离散或元素范围未知的情况。C语言没有提过散列表，可以采用三方开源uthash。
C代码如下（含测试用例）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "uthash.h"
struct ListNode {
char data;
struct ListNode* link;
};
struct hashTable {
int key;
int val;
UT_hash_handle hh;
};
struct hashTable* hashtable;
struct hashTable* find(int ikey) {
struct hashTable* tmp;
HASH_FIND_INT(hashtable, &ikey, tmp);
return tmp;
}
void insert(int ikey, int ival) {
struct hashTable* it = find(ikey);
if (it == NULL) {
struct hashTable* tmp = malloc(sizeof(struct hashTable));
tmp->key = ikey, tmp->val = ival;
HASH_ADD_INT(hashtable, key, tmp);
} else {
it->val = ival;
}
}
struct ListNode *deleteDuplicates(struct ListNode* head) {
hashtable = NULL;
struct ListNode *prev = head;
struct ListNode *curr = head->link;
while (curr) {
struct hashTable *it = find(abs(curr->data));
if (it != NULL) {
prev->link = curr->link;
struct ListNode *temp = curr;
curr = curr->link;
free(temp);
} else {
insert(abs(curr->data), 1);
prev = prev->link;
curr = curr->link;
}
}
return head;
}
struct ListNode* createLinkedList(int *a, int n) {
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* tail = head;
for (int i = 0; i < n; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = a[i];
node->link = NULL;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
int a[] = {21, -15, -15, -7, 15};
struct ListNode* head = createLinkedList(a, 5);
struct ListNode* newhead = deleteDuplicates(head);
struct ListNode* curr = head->link;
printf("head");
while (curr != NULL) {
printf("->%d", curr->data);
curr = curr->link;
}
return 0;
}
C++代码如下（含测试用例）：
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
struct ListNode {
int data;
ListNode *link;
};
ListNode* deleteDuplicates(ListNode* head) {
unordered_set<int>st;
ListNode *prev = head;
ListNode *curr = head->link;
while (curr) {
if (st.count(abs(curr->data))) {
prev->link = curr->link;
ListNode *temp = curr;
curr = curr->link;
delete temp;
} else {
st.insert(abs(curr->data));
prev = prev->link;
curr = curr->link;
}
}
return head;
}
ListNode* createLinkedList(vector<int> nums) {
ListNode* head = new ListNode();
ListNode* tail = head;
for (int i = 0; i < nums.size(); i++) {
ListNode* node = new ListNode();
node->data = nums[i];
node->link = nullptr;
tail->link = node;
tail = tail->link;
}
return head;
}
int main(int argc, const char * argv[]) {
vector<int>nums{21, -15, -15, -15, -7, 15, 15};
ListNode* head = createLinkedList(nums);
ListNode* newhead = deleteDuplicates(head);
ListNode* curr = newhead->link;
cout << "head";
while (curr) {
cout << "->" << curr->data;
curr = curr->link;
}
return 0;
}
复杂度分析
- 时间复杂度： O(m) ，只需要遍历一次链表。
- 空间复杂度： O(m) ，辅助散列表空间为 O(m) 。
。
。
。
。
。
。
，传播时延为 τ=250 ms ，主机乙发送一个确认帧的时延为 t2 ，因为乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，所以 t2=0 ，传播时延为 τ=250 ms 。一个周期 T=t1+τ+t2+τ=562.5 ms 。因为数据链路层采用滑动窗口协议传输数据，为使信道利用率达到最高，在一个周期内，发送方可以连续发送多个数据帧，将位于发送窗口中的帧全部发送出去。
，解得 WT≥7.2 。取 WT=8 。
。
。
。
。
等价于 
。根据虚拟地址格式，因为虚拟地址 0100 0000H = 
B 和 0111 2048H = 
B 的页目录号都是0000 0001 00B=4，所以进行地址转换时需访问一级页表的同一个页表项，对应同一个二级页表，即 4 号二级页表，两个虚拟地址在二级页表中的页表项不同。如下图所示：
The road of your choice, you have to go on !
粤ICP备16082171号-1
