961_重复 N 次的元素

风扫地

1. /*
   
2. 在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。
   
3. 
   
4. 返回重复了 N 次的那个元素。
   
5. 
   
6. 
   
7. 
   
8. 示例 1：
   
9. 
   
10. 输入：[1,2,3,3]
    
11. 输出：3
    
12. 示例 2：
    
13. 
    
14. 输入：[2,1,2,5,3,2]
    
15. 输出：2
    
16. 示例 3：
    
17. 
    
18. 输入：[5,1,5,2,5,3,5,4]
    
19. 输出：5
    
20. 
    
21. 
    
22. 提示：
    
23. 
    
24. 4 <= A.length <= 10000
    
25. 0 <= A[i] < 10000
    
26. A.length 为偶数
    
27. 
    
28. 
    
29. */

复制代码

1. struct node_t
   
2. {
   
3.     int            key;
   
4.     int            value;  /* key 出现的次数 */
   
5.     struct node_t* left;
   
6.     struct node_t* right;
   
7. };
   
8. 
   
9. 
   
10. 
    
11. struct node_t* root = NULL;
    
12. 
    
13. 
    
14. 
    
15. void node_init(struct node_t* node_s, int key)
    
16. {
    
17.     if(node_s !=NULL)
    
18.     {
    
19.         node_s -> key   = key   ;
    
20.         node_s -> value = 1     ;
    
21.         node_s -> left  = NULL  ;
    
22.         node_s -> right = NULL  ;
    
23.     }
    
24. }
    
25. 
    
26. struct node_t* bst_insert(struct node_t* node_s, int key )
    
27. {
    
28.     if(node_s == NULL)
    
29.     {
    
30.         node_s = (struct node_t*)malloc(sizeof(struct node_t));
    
31.         node_init(node_s,key);
    
32.         return node_s;
    
33.     }
    
34.    
    
35.     if(key == node_s->key)
    
36.     {
    
37.         node_s->value ++;
    
38.         return node_s;
    
39.     }
    
40.     else if(key < node_s->key)
    
41.     {
    
42.         node_s->left = bst_insert(node_s->left, key );
    
43.     }
    
44.     else // key > node_s->key
    
45.     {
    
46.         node_s->right = bst_insert(node_s->right, key );
    
47.     }
    
48. 
    
49. 
    
50.     return node_s;
    
51. 
    
52. }
    
53. 
    
54. int* bst_dfs( struct node_t* node_s , int value)
    
55. {
    
56.    
    
57.     int* ret_val_left  = NULL;
    
58.     int* ret_val_right = NULL;
    
59.     if(node_s == NULL)
    
60.     {
    
61.         return NULL;
    
62.     }
    
63.     if(node_s->value == value)
    
64.     {
    
65.         return &node_s->key;
    
66.     }
    
67.     else
    
68.     {
    
69.         ret_val_left  = bst_dfs(node_s->left,value);
    
70.         ret_val_right = bst_dfs(node_s->right,value);
    
71.         
    
72.         if(ret_val_left!=NULL)
    
73.         {
    
74.             return ret_val_left;
    
75.         }
    
76.         else
    
77.         {
    
78.             return ret_val_right;
    
79.         }
    
80.     }
    
81. }
    
82. 
    
83. 
    
84. void bst_delete(struct node_t* bd_node_s)
    
85. {
    
86.     if(bd_node_s == NULL)
    
87.     {
    
88.         return;
    
89.     }
    
90.    
    
91.     if(bd_node_s->left !=NULL)
    
92.     {
    
93.         bst_delete(bd_node_s->left);
    
94.         bd_node_s->left = NULL;
    
95.     }
    
96.     if(bd_node_s->right !=NULL)
    
97.     {
    
98.         bst_delete(bd_node_s->right);
    
99.         bd_node_s->right = NULL;
    
100.     }
     
101.    
     
102.     free(bd_node_s);
     
103.     bd_node_s = NULL;
     
104. }
     
105. 
     
106. int repeatedNTimes(int* A, int ASize)
     
107. {
     
108.     int* temp_ptr = NULL;
     
109.     int ret_val = 0;
     
110.    
     
111.     for(int i = 0; i < ASize ; i++)
     
112.     {
     
113.         root = bst_insert(root, A[i]);
     
114.     }
     
115.     temp_ptr = bst_dfs( root,ASize / 2 );
     
116.     ret_val = *temp_ptr;
     
117.     bst_delete(root);
     
118.     root = NULL;
     
119.     return ret_val;
     
120. }

复制代码

测试结果：

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

复制代码

风扫地

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

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

风扫地

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

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

风扫地

优化后的实现：

1. struct node_t
   
2. {
   
3.     int            key;
   
4.     int            value;  /* key 出现的次数 */
   
5.     struct node_t* left;
   
6.     struct node_t* right;
   
7. };
   
8. 
   
9. 
   
10. 
    
11. struct node_t* root = NULL;
    
12. int* temp_ptr = NULL;
    
13. 
    
14. 
    
15. 
    
16. void node_init(struct node_t* node_s, int key)
    
17. {
    
18.     if(node_s !=NULL)
    
19.     {
    
20.         node_s -> key   = key   ;
    
21.         node_s -> value = 1     ;
    
22.         node_s -> left  = NULL  ;
    
23.         node_s -> right = NULL  ;
    
24.     }
    
25. }
    
26. 
    
27. struct node_t* bst_insert(struct node_t* node_s, int key )
    
28. {
    
29.     if(node_s == NULL)
    
30.     {
    
31.         node_s = (struct node_t*)malloc(sizeof(struct node_t));
    
32.         node_init(node_s,key);
    
33.         return node_s;
    
34.     }
    
35.    
    
36.     if(key == node_s->key)
    
37.     {
    
38.         node_s->value ++;
    
39.         temp_ptr = &(node_s->key);
    
40.         return node_s;
    
41.     }
    
42.     else if(key < node_s->key)
    
43.     {
    
44.         node_s->left = bst_insert(node_s->left, key );
    
45.     }
    
46.     else // key > node_s->key
    
47.     {
    
48.         node_s->right = bst_insert(node_s->right, key );
    
49.     }
    
50. 
    
51. 
    
52.     return node_s;
    
53. 
    
54. }
    
55. 
    
56. int* bst_dfs( struct node_t* node_s , int value)
    
57. {
    
58.    
    
59.     int* ret_val_left  = NULL;
    
60.     int* ret_val_right = NULL;
    
61.     if(node_s == NULL)
    
62.     {
    
63.         return NULL;
    
64.     }
    
65.     if(node_s->value == value)
    
66.     {
    
67.         return &node_s->key;
    
68.     }
    
69.     else
    
70.     {
    
71.         ret_val_left  = bst_dfs(node_s->left,value);
    
72.         ret_val_right = bst_dfs(node_s->right,value);
    
73.         
    
74.         if(ret_val_left!=NULL)
    
75.         {
    
76.             return ret_val_left;
    
77.         }
    
78.         else
    
79.         {
    
80.             return ret_val_right;
    
81.         }
    
82.     }
    
83. }
    
84. 
    
85. 
    
86. void bst_delete(struct node_t* bd_node_s)
    
87. {
    
88.     if(bd_node_s == NULL)
    
89.     {
    
90.         return;
    
91.     }
    
92.    
    
93.     if(bd_node_s->left !=NULL)
    
94.     {
    
95.         bst_delete(bd_node_s->left);
    
96.         bd_node_s->left = NULL;
    
97.     }
    
98.     if(bd_node_s->right !=NULL)
    
99.     {
    
100.         bst_delete(bd_node_s->right);
     
101.         bd_node_s->right = NULL;
     
102.     }
     
103.    
     
104.     free(bd_node_s);
     
105.     bd_node_s = NULL;
     
106. }
     
107. 
     
108. int repeatedNTimes(int* A, int ASize)
     
109. {
     
110. 
     
111.     int ret_val = 0;
     
112.    
     
113.     for(int i = 0; i < ASize ; i++)
     
114.     {
     
115.         root = bst_insert(root, A[i]);
     
116.         if(temp_ptr!=NULL)
     
117.         {
     
118.             break;
     
119.         }
     
120.     }
     
121.     ret_val = *temp_ptr;
     
122.    
     
123.     bst_delete(root);
     
124.     root = NULL;
     
125.     temp_ptr = NULL;
     
126.     return ret_val;
     
127. }

复制代码

其中dfs代码可以省略（因为是错的）。

有了不错的改善：

1. 执行用时 : 40 ms, 在N-Repeated Element in Size 2N Array的C提交中击败了56.23% 的用户
   
2. 内存消耗 : 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% 的用户