数组中出现次数超过一半的数字

时间：2022-11-21 11:04:55
题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

 

输入：

每个测试案例包括2行：

第一行输入一个整数n（1<=n<=100000），表示数组中元素的个数。

第二行输入n个整数，表示数组中的每个元素，这n个整数的范围是[1,1000000000]。

 

输出：

对应每个测试案例，输出出现的次数超过数组长度的一半的数，如果没有输出-1。

 

样例输入： 
9
1 2 3 2 2 2 5 4 2
样例输出： 
2
 1 #include <stdio.h>
 2 void main()
 3 {
 4     int n;
 5     while(scanf("%d",&n)!=EOF)
 6     {
 7         int array[100000];
 8         for (int i=0; i< n; i++)
 9         {
10             scanf("%d",&array[i]);
11         }
12         int result = array[0];
13         int times = 1;
14         i = 0;
15         while(i < n)
16         {
17             if (times == 0)
18             {
19                 result = array[i];
20                 times = 1;
21             }
22             if (result == array[i])
23                 times++;
24             else
25                 times--;
26             i++;
27         }
28         int count =0;
29         for (int j=0; j < n; j++)
30         {
31             if(array[j]  == result)
32                 count++;
33         }
34         if (2*count > n)
35             printf("%d\n",result);
36         else
37             printf("-1\n");
38     }
39 }

another methord

 1 #include <stdio.h>
 2 
 3 int partition(int array[], int start, int end)
 4 {
 5     int key = array[start];
 6     while(start < end)
 7     {
 8         while(start<end && array[end]>=key) end--;
 9         if (start<end)
10         {
11             array[start] = array[end];
12             start++;
13         }
14         else
15         {
16             break;
17         }
18 
19         while(start <end && array[start] < key) start++;
20         if (start < end)
21         {
22             array[end] = array[start];
23             end--;
24         }
25     }
26     array[start] = key;
27     return start;
28 }
29 
30 int checkMoreHalf(int array[],int lenght,int number)
31 {
32     int total = 0;
33     for (int i=0; i<lenght; i++)
34     {
35         if (array[i] == number)
36             total++;
37     }
38     if (2*total > lenght)
39     {
40         return 1;
41     }
42     return -1;
43 }
44 
45 void MoreThanHalfNum(int array[], int length)
46 {
47     int middle = length >> 1;
48     int start  = 0;
49     int end    = length -1;
50     int index = partition(array,start,end);
51     while(index != middle)
52     {
53         if (index > middle)
54         {
55             end = index -1;
56         }
57         else
58         {
59             start = index+1;
60         }
61         index = partition(array,start,end);
62     }
63     if (checkMoreHalf(array,length,array[index]) == 1)
64     {
65         printf("%d\n",array[index]);
66     }
67     else
68     {
69         printf("-1\n");
70     }
71 }
72 
73 void main()
74 {
75     int n;
76     while(scanf("%d",&n)!=EOF)
77     {
78         int array[100000];
79         for (int i=0; i< n; i++)
80         {
81             scanf("%d",&array[i]);
82         }
83         MoreThanHalfNum(array,n);
84     }
85 }

 

标签：

相关文章