数组面试题

#include<iostream>
using namespace std;
//数组求和
int sum(int *a, int n)
{
	return n == 0 ? 0 : sum(a, n - 1) + a[n - 1];
}
//递归法数组求和
int sum2(int *a, int n)
{
	int s = 0;
	for (int i = n - 1; i > 0; i--){
		s += a[i];
	}
	return s;
}
//求数组的最大最小值
void Max_Min(int *a, int n, int &max_value, int &min_value)
{
	max_value = a[0];
	min_value = a[0];
	for (int i = 0; i < n; i++){
		if (a[i] > max_value)
			max_value = a[i];
		if (a[i] < min_value)
			min_value = a[i];
	}
}
//求数组中出现次数超过一半的元素
int halftime_val(int *a, int n)
{
	typedef struct valuetype{
		int num;
		int time;
	}value;
	int target_val = -1;
	value* data = new value[n];

	for (int i = 0; i < n; i++) //统计数组元素出现的次数
	{
		data[i].num = a[i];
		data[i].time = 1;
		for (int j = 0; j < i; j++){
			if (data[i].num == data[j].num)
				data[i].time++;
		}
	}
	for (int i = 0; i < n; i++){
		if (data[i].time > n / 2){
			target_val = data[i].num;
		}
	}
	delete data;
	return target_val;
}

// 找出数组中出现次数超过一半的元素
int Find(int* a, int n)
{
	int curValue = a[0];
	int count = 1;

	for (int i = 1; i < n; ++i)
	{
		if (a[i] == curValue)
			count++;
		else
		{
			count--;
			if (count < 0)
			{
				curValue = a[i];
				count = 1;
			}
		}
	}

	return curValue;
}

//求数组中距离最小的两点
//给定一个含有n个元素的整型数组，找出数组中的两个元素x和y使得abs(x - y)值最小
//先对数组排序，然后遍历一次即可
int compare(const void* a, const void* b)
{
	return(*(int*)a - *(int*)b);
}
void Min_Distance(int *a, int n)
{
	qsort(a, n, sizeof(int), compare);
	int min_distace = 0;
	int temp = 0, x1 = 0, x2 = 0;
	min_distace = a[1] - a[0];
	for (int i = 1; i < n - 1; i++)
	{
		temp = abs(a[i + 1] - a[i]);
		if (temp < min_distace)
		{
			min_distace = temp;
			x1 = a[i + 1];
			x2 = a[i];
		}
	}
	cout << min_distace << endl;
	cout << x1 <<" "<< x2 << endl;
}
//求两个有序数组的共同元素
/*
给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如
a = 0, 1, 2, 3, 4
b = 1, 3, 5, 7, 9
输出 1, 3
***************************************************************
分析：充分利用数组有序的性质，用两个指针i和j分别指向a和b，比较a[i]和b[j]，根据比较结果移动指针，则有如下三种情况

1. a[i] < b[j]，则i增加1，继续比较
2. a[i] == b[j]，则i和j皆加1，继续比较
3. a[i] < b[j]，则j加1，继续比较
重复以上过程直到i或j到达数组末尾。
*/
void Find_Commom1(int *a, int *b, int n)
{
	int i = 0, j = 0;
	while (i < n && j < n){
		if (a[i] < b[j]) i++;
		if (a[i] == b[j]){
			cout << a[i] << " ";
			i++;
			j++;
		}
		if (a[i] > b[j]) j++;
	}
	cout << endl;
}
void Find_Commom(int* a, int *b, int n)
{
	int i, j;
	for (i = 0; i < n; i++){
		for (j = 0; j < n; j++){
			if (a[i] == b[j])
				cout << a[i] << " ";
		}
	}
	cout << endl;
}

int main()
{
	int a[4] = { 2, 4, 6, 8 };
	int b[5] = { 1, 5, 7, 9 };
	Find_Commom(a, b, 4);
	Find_Commom1(a, b, 4);
}