论坛 › 数据结构与算法 › 961_重复 N 次的元素

风扫地 发表于 2019-5-20 15:05:29

961_重复 N 次的元素

/*
在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。

返回重复了 N 次的那个元素。



示例 1：

输入：
输出：3
示例 2：

输入：
输出：2
示例 3：

输入：
输出：5


提示：

4 <= A.length <= 10000
0 <= A < 10000
A.length 为偶数


*/



struct node_t
{
    int            key;
    int            value;/* key 出现的次数 */
    struct node_t* left;
    struct node_t* right;
};



struct node_t* root = NULL;



void node_init(struct node_t* node_s, int key)
{
    if(node_s !=NULL)
    {
      node_s -> key   = key   ;
      node_s -> value = 1   ;
      node_s -> left= NULL;
      node_s -> right = NULL;
    }
}

struct node_t* bst_insert(struct node_t* node_s, int key )
{
    if(node_s == NULL)
    {
      node_s = (struct node_t*)malloc(sizeof(struct node_t));
      node_init(node_s,key);
      return node_s;
    }
   
    if(key == node_s->key)
    {
      node_s->value ++;
      return node_s;
    }
    else if(key < node_s->key)
    {
      node_s->left = bst_insert(node_s->left, key );
    }
    else // key > node_s->key
    {
      node_s->right = bst_insert(node_s->right, key );
    }


    return node_s;

}

int* bst_dfs( struct node_t* node_s , int value)
{
   
    int* ret_val_left= NULL;
    int* ret_val_right = NULL;
    if(node_s == NULL)
    {
      return NULL;
    }
    if(node_s->value == value)
    {
      return &node_s->key;
    }
    else
    {
      ret_val_left= bst_dfs(node_s->left,value);
      ret_val_right = bst_dfs(node_s->right,value);
      
      if(ret_val_left!=NULL)
      {
            return ret_val_left;
      }
      else
      {
            return ret_val_right;
      }
    }
}


void bst_delete(struct node_t* bd_node_s)
{
    if(bd_node_s == NULL)
    {
      return;
    }
   
    if(bd_node_s->left !=NULL)
    {
      bst_delete(bd_node_s->left);
      bd_node_s->left = NULL;
    }
    if(bd_node_s->right !=NULL)
    {
      bst_delete(bd_node_s->right);
      bd_node_s->right = NULL;
    }
   
    free(bd_node_s);
    bd_node_s = NULL;
}

int repeatedNTimes(int* A, int ASize)
{
    int* temp_ptr = NULL;
    int ret_val = 0;
   
    for(int i = 0; i < ASize ; i++)
    {
      root = bst_insert(root, A);
    }
    temp_ptr = bst_dfs( root,ASize / 2 );
    ret_val = *temp_ptr;
    bst_delete(root);
    root = NULL;
    return ret_val;
}


测试结果：
执行用时 : 132 ms, 在N-Repeated Element in Size 2N Array的C提交中击败了14.72% 的用户
内存消耗 : 38.9 MB, 在N-Repeated Element in Size 2N Array的C提交中击败了5.71% 的用户
102 / 102 个通过测试用例
状态：通过
执行用时：124 ms
提交时间：7 分钟之前

风扫地 发表于 2019-5-20 15:08:48

用BST逐一插入，然后搜索就可以了。。

不过时空复杂度已经炸飞了。。

风扫地 发表于 2019-5-20 15:10:09

回到题意：在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。

所以在BST插入的过程中，不需要插入完全，只要在插入时发现已经存在就可以中断插入然后直接返回了。

风扫地 发表于 2019-5-20 15:14:05

本帖最后由 风扫地 于 2019-5-21 09:44 编辑

优化后的实现：
struct node_t
{
    int            key;
    int            value;/* key 出现的次数 */
    struct node_t* left;
    struct node_t* right;
};



struct node_t* root = NULL;
int* temp_ptr = NULL;



void node_init(struct node_t* node_s, int key)
{
    if(node_s !=NULL)
    {
      node_s -> key   = key   ;
      node_s -> value = 1   ;
      node_s -> left= NULL;
      node_s -> right = NULL;
    }
}

struct node_t* bst_insert(struct node_t* node_s, int key )
{
    if(node_s == NULL)
    {
      node_s = (struct node_t*)malloc(sizeof(struct node_t));
      node_init(node_s,key);
      return node_s;
    }
   
    if(key == node_s->key)
    {
      node_s->value ++;
      temp_ptr = &(node_s->key);
      return node_s;
    }
    else if(key < node_s->key)
    {
      node_s->left = bst_insert(node_s->left, key );
    }
    else // key > node_s->key
    {
      node_s->right = bst_insert(node_s->right, key );
    }


    return node_s;

}

int* bst_dfs( struct node_t* node_s , int value)
{
   
    int* ret_val_left= NULL;
    int* ret_val_right = NULL;
    if(node_s == NULL)
    {
      return NULL;
    }
    if(node_s->value == value)
    {
      return &node_s->key;
    }
    else
    {
      ret_val_left= bst_dfs(node_s->left,value);
      ret_val_right = bst_dfs(node_s->right,value);
      
      if(ret_val_left!=NULL)
      {
            return ret_val_left;
      }
      else
      {
            return ret_val_right;
      }
    }
}


void bst_delete(struct node_t* bd_node_s)
{
    if(bd_node_s == NULL)
    {
      return;
    }
   
    if(bd_node_s->left !=NULL)
    {
      bst_delete(bd_node_s->left);
      bd_node_s->left = NULL;
    }
    if(bd_node_s->right !=NULL)
    {
      bst_delete(bd_node_s->right);
      bd_node_s->right = NULL;
    }
   
    free(bd_node_s);
    bd_node_s = NULL;
}

int repeatedNTimes(int* A, int ASize)
{

    int ret_val = 0;
   
    for(int i = 0; i < ASize ; i++)
    {
      root = bst_insert(root, A);
      if(temp_ptr!=NULL)
      {
            break;
      }
    }
    ret_val = *temp_ptr;
   
    bst_delete(root);
    root = NULL;
    temp_ptr = NULL;
    return ret_val;
}
其中dfs代码可以省略（因为是错的）。

有了不错的改善：
执行用时 : 40 ms, 在N-Repeated Element in Size 2N Array的C提交中击败了56.23% 的用户
内存消耗 : 8.7 MB, 在N-Repeated Element in Size 2N Array的C提交中击败了77.14% 的用户

风扫地 发表于 2019-5-21 10:07:47

用python就简单多了

class Solution:
    def repeatedNTimes(self, A: List) -> int:
      s = set();
      for each in A:
            if each not in s:
                s.add(each)
            else:
                return each



执行用时 : 64 ms, 在N-Repeated Element in Size 2N Array的Python3提交中击败了94.11% 的用户
内存消耗 : 14 MB, 在N-Repeated Element in Size 2N Array的Python3提交中击败了96.83% 的用户

查看完整版本: 961_重复 N 次的元素