JZ-C-29

剑指offer第二十九题:数组中出现次数超过一半的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//============================================================================
// Name        : JZ-C-29.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 数组中出现次数超过一半的数字
//============================================================================
 
#include <iostream>
#include "Array.h"
#include <stdio.h>
using namespace std;
 
bool g_bInputInvalid = false;
/**
 *检查数组是否合法
 */
bool CheckInvalidArray(int* numbers, int length) {
	g_bInputInvalid = false;
	if (numbers == NULL && 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;
}
 
// ====================方法1:分治法,参考快速排序====================
int MoreThanHalfNum_Solution1(int* numbers, int length) {
	if (CheckInvalidArray(numbers, length)) {
		return 0;
	}
	int middle = length >> 1; //右移1位
	int start = 0;
	int end = length - 1;
	int index = Partition(numbers, length, start, end);
	while (index != middle) {
		if (index < middle) {
			index = Partition(numbers, length, index + 1, end);
		} else {
			index = Partition(numbers, length, start, index - 1);
		}
	}
	int result = numbers[middle];
	if (!CheckMoreThanHalf(numbers, length, result)) {
		result = 0;
	}
	return result;
}
// ====================方法2:利用数字出现次数大于数组长度的一半====================
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 (result != numbers[i]) {
			times--;
		} else {
			times++;
		}
	}
	if (!CheckMoreThanHalf(numbers, length, result)) {
		result = 0;
	}
	return result;
}
// ====================测试代码====================
void Test(char* testName, int* numbers, int length, int expectedValue,
		bool expectedFlag) {
	if (testName != NULL)
		printf("%s begins: \n", testName);
 
	int* copy = new int[length];
	for (int i = 0; i < length; ++i)
		copy[i] = numbers[i];
 
	printf("Test for solution1: ");
	int result = MoreThanHalfNum_Solution1(numbers, length);
	if (result == expectedValue && g_bInputInvalid == expectedFlag)
		printf("Passed.\n");
	else
		printf("Failed.\n");
 
	printf("Test for solution2: ");
	result = MoreThanHalfNum_Solution2(copy, length);
	if (result == expectedValue && g_bInputInvalid == expectedFlag)
		printf("Passed.\n");
	else
		printf("Failed.\n");
 
	delete[] copy;
}
 
// 存在出现次数超过数组长度一半的数字
void Test1() {
	int numbers[] = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
	Test("Test1", numbers, sizeof(numbers) / sizeof(int), 2, false);
}
 
// 不存在出现次数超过数组长度一半的数字
void Test2() {
	int numbers[] = { 1, 2, 3, 2, 4, 2, 5, 2, 3 };
	Test("Test2", numbers, sizeof(numbers) / sizeof(int), 0, true);
}
 
// 出现次数超过数组长度一半的数字都出现在数组的前半部分
void Test3() {
	int numbers[] = { 2, 2, 2, 2, 2, 1, 3, 4, 5 };
	Test("Test3", numbers, sizeof(numbers) / sizeof(int), 2, false);
}
 
// 出现次数超过数组长度一半的数字都出现在数组的后半部分
void Test4() {
	int numbers[] = { 1, 3, 4, 5, 2, 2, 2, 2, 2 };
	Test("Test4", numbers, sizeof(numbers) / sizeof(int), 2, false);
}
 
// 输入空指针
void Test5() {
	int numbers[] = { 1 };
	Test("Test5", numbers, 1, 1, false);
}
 
// 输入空指针
void Test6() {
	Test("Test6", NULL, 0, 0, true);
}
 
int main(int argc, char** argv) {
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();
	Test6();
 
	return 0;
}

关于Partition方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 著作权所有者:何海涛
 
#include <stdlib.h>
#include <stdio.h>
#include "Array.h"
#include <exception>
 
// Random Partition
int RandomInRange(int min, int max) {
	int random = rand() % (max - min + 1) + min;
	return random;
}
 
void Swap(int* num1, int* num2) {
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
 
int Partition(int data[], int length, int start, int end) {
	if (data == NULL || length <= 0 || start < 0 || end >= length) {
		printf("Invalid Parameters");
		throw new std::exception();//这里括号里为什么不能加msg???!!!
	}
	int index = RandomInRange(start, end);
	Swap(&data[index], &data[end]);
 
	int small = start - 1;
	for (index = start; index < end; ++index) {
		if (data[index] < data[end]) {
			++small;
			if (small != index)
				Swap(&data[index], &data[small]);
		}
	}
 
	++small;
	Swap(&data[small], &data[end]);
 
	return small;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注