961_重复 N 次的元素

风扫地

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

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

 

示例 1：

输入：[1,2,3,3]
输出：3
示例 2：

输入：[2,1,2,5,3,2]
输出：2
示例 3：

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

提示：

4 <= A.length <= 10000
0 <= A[i] < 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[i]);
    }
    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 分钟之前

风扫地

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

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

风扫地

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

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

风扫地

优化后的实现：

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[i]);
        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% 的用户

风扫地

用python就简单多了

class Solution:
    def repeatedNTimes(self, A: List[int]) -> 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% 的用户