JSMS42- The number that occurs more than half the time in the array – the sword means offer29

Given an array a, return the elements in array A that occur more than half the time.

The number of occurrences of each element is stored in an array, either by index or by hash, but this will consume space complexity. The second method of parsing is highly recommended, and also very clever and clever, by using a variable int num; Record a[x] in array, then int times; Num ==a[I], ++times; Otherwise; If times==0, select * from num; otherwise, times–; Look at the code

#include <stdio.h> #include <stdlib.h> int MoreThanHalfNum(int *a,int len) { int times=0; int num=a[0]; int tmp; for(int i=1; i<len; i++) { if(num==a[i]) { ++times; }else { if(times==0) { num=a[i]; }else { times--; } } } return num; } int main() {int a[]={3,1,2,3,1, 3,1,2, 2, 2, 2, 2,3, 2,3}; int len=sizeof(a)/sizeof(a[0]); int ret=MoreThanHalfNum(a,len); printf("%d\n",ret); }Copy the code