1743. 从相邻元素对还原数组-哈希表法

1743. 从相邻元素对还原数组-哈希表法

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。

给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。

题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。

返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。

示例 1：

输入：adjacentPairs = [[2,1],[3,4],[3,2]]
输出：[1,2,3,4]
解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。

示例 2：

输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
输出：[-2,4,1,-3]
解释：数组中可能存在负数。
另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。

示例 3：

输入：adjacentPairs = [[100000,-100000]]
输出：[100000,-100000]

个人感觉这题如果真的用c语言去做的话，确实比较复杂，解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define size 15675
struct hash{
    int count;
    int adj;
 
     int val;
 struct hash *next;
};
void hash_add(int val,int adj,struct hash *h,int count){
    struct hash *p=(struct hash*)malloc(sizeof(struct hash));
    p->val=val;
    p->next=h->next;
    p->adj=adj;
    p->count=count;
    h->next=p;
}
int find_hash(int val,int adj,struct hash *h){
    h=h->next;
    while(h){
        if(h->val==val){
              h->count++;
              return 1;

        }
        
          h=h->next;
    }
    return 0;
}

int find_hash_adj(int val,struct hash *h,int pre){
    h=h->next;
    while(h){
        if(h->val==val&&h->adj!=pre){
            return h->adj;
        }
          h=h->next;
    }
    return 0;
}




int* restoreArray(int** adjacentPairs, int adjacentPairsSize, int* adjacentPairsColSize, int* returnSize){
    int *num=(int *)malloc(sizeof(int)*adjacentPairsSize*2);
    
     struct hash *h=(struct hash *)malloc(sizeof(struct hash)*size);
    int i;
    int *a=(int *)malloc(sizeof(int)*2);
    for(i=0;i<size;i++){
        (h+i)->next=NULL;
    }
    int pz=0;

    for(int i=0;i<adjacentPairsSize;i++){
        int a=adjacentPairs[i][0];
        int b=adjacentPairs[i][1];
        
       if(find_hash(a,b,h+abs(a)%size)==0){

            hash_add(a,b,h+abs(a)%size,1);
             }
             else{
                  hash_add(a,b,h+abs(a)%size,2);

             }
      

         if(find_hash(b,a,h+abs(b)%size)==0){
              hash_add(b,a,h+abs(b)%size,1);

         }
         else{

            hash_add(b,a,h+abs(b)%size,2);

         }
         

        
        
    }
    int val_start;
    int val_end;
    int end=0;
   

    for(int i=0;i<size;i++){
        struct hash *p=(h+i)->next;
       
        while(p){
           
             if(p->count==1&&end==1){
                val_end=p->val;
               end++;
              
            }
            if(p->count==1&&end==0){
                val_start=p->val;
               end++;
              
            }
            
            p=p->next;
        }
        if(end==2){
            break;
        }

    }
 
    num[pz++]=val_start;
    int now=val_start;
    int pre=-1;
    int adj=0;

    while(true){
       
       if(now==val_start){
          
         adj=find_hash_adj(now,h+abs(now)%size,pre);
          pre=now;
         now=adj;
          }
          else{
              
               adj=find_hash_adj(now,h+abs(now)%size,pre);
               pre=now;
               now=adj;


          }


         num[pz++]=adj;
         if(adj==val_end){break;}

    }


   
  *returnSize=pz;
    return num;
   
    

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151