## 题目1 数组中出现次数超过一半的数字

### 代码1

int MoreThanHalfNum_Solution(vector<int> numbers) { int len = numbers.size(); int count=0; if(len==0) return 0; if(len==1) return numbers[0]; sort(numbers.begin(), numbers.end()); int mid = numbers[len/2]; for(int i=0;i<len;i++) { if(numbers[i]==mid) ++count; } return (count>(len/2))?mid:0;}

### 代码2

bool g_bInputInvaild = false;bool CheckInvalidArray(int* numbers, int length){ g_bInputInvalid = false; if (numbers == nullptr && length <= 0) g_bInputInvalid = true; return g_bInputInvalid;}bool CheckMoreThanHalf(int* numbers, int length, int number){ int times = 0; for (int i = 0; i < length; ++i) { if (numbers[i] == number) times++; } bool isMoreThanHalf = true; if (times * 2 <= length) { g_bInputInvalid = true; isMoreThanHalf = false; } return isMoreThanHalf;}int Partition(int data[],int length,int start,int end)
{ if(data==NULL || length<=0||start<0 || end>=length) { cout<<"error1!"<<endl; exit(0); } int index=RandomInRange(start,end); swap_element(&data[index],&data[end]); int small=start-1; for(index=start;index<end;index++) { if(data[index]<data[end]) { ++small; if(small != index) { swap_element(&data[index],&data[small]); } } } ++small; swap_element(&data[small],&data[end]); return small;}
 int MoreThanHalfNum_Solution(vector<int> numbers) { if(CheckInvalidArray(numbers,length) return 0; int middle=length>>1; int start=0; int end=length-1; int index=Partition(numbers,length,start,end); while(index!=middle) { if(index>middle) { end=index-1; index=Partition(numbers,length,start,end); } else{ start=index+1; index=Partition(numbers,length,start,end); } } int result=numbers[middle]; if(!CheckMoreThanHalf(numbers,length,result)) result=0; return result;}

### 代码3

int MoreThanHalfNum_Solution2(int* numbers, int length) { if (CheckInvalidArray(numbers, length)) return 0; int result = numbers[0]; int times = 1; for (int i = 1; i < length; ++i) { if (times == 0) { result = numbers[i]; times = 1; } else if (numbers[i] == result) times++; else times--; } if (!CheckMoreThanHalf(numbers, length, result)) result = 0; return result; }

## 题目2 最小的k个数

### 代码

 void GetLeastNumbers(int* input, int n, int* output, int k) { if(input==nullptr||output==nullptr||k>n||n<=0||k<=0) return; int start=0; int end=n-1; int index=Partition(intput,n,start,end); while(index!=k-1) { if(index>k-1) { end=index-1; index=Partition(input,n,start,end); } else { start=index+1; index=Partition(intput,n,start,end); } } for(int i=0;i<k;++i) output[i]=input[i]; }

## 题目3 连续子数组的最大和

### 题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

### 代码

int FindGreatestSumOfSubArray(vector<int> array) { int ThisSum =0; int MaxSum = array[0]; int N = array.size(); int i; for(i=0;i<N;i++) { ThisSum += array[i]; if(ThisSum>MaxSum) MaxSum=ThisSum; else if(ThisSum<0) ThisSum=0; } return MaxSum;}

## 题目4 整数中出现1的次数

### 代码

int NumberOf1Between1AndN_Solution(int n){ int count = 0; if(n==0) return count; for(int i=1;i<=n;i++) { int tmp=i; while(tmp) { if(tmp%10==1) ++count; tmp /=10; } }return count;}

## 题目5 把数组排成最小的数字

### 代码

 static bool cmp(int a, int b){//意思是若ab<ba，则返回(a,b)；若ab>ba，则返回(b,a)。 string A = to_string(a) + to_string(b); string B = to_string(b) + to_string(a); return A < B;} string PrintMinNumber(vector<int> numbers) { int len =numbers.size(); if(len==0) return ""; string result; sort(numbers.begin(),numbers.end(),cmp); for(int i=0;i<len;i++) result += to_string(numbers[i]); return result; }