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

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

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;
   
    

}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/2991812.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存