【C语言实现-左神算法课p2习题】

左神算法课p2习题

• • 1.找出现奇数次的数字
  • 2.三大排序之冒泡-选择-插入
  • 3.二分法应用扩展

1.找出现奇数次的数字

• 提取一个二进制数右数第一个1:
  a(~a+1)
• 勤添加括号，避免犯运算符号优先级问题:
  if ((nums[i] & dif) != 0) 对 if (nums[i] & dif != 0) 错

---

1. 给定一组数字，其中只有一种数字出现奇数次，其余均出现偶数次，找出出现奇数次的这个数
2. 给定一组数字，其中只有两种数字出现奇数次，其余均出现偶数次，找出出现奇数次的这两个数

---

#include
using namespace std;
//设计一个函数，实现：给定一组数字，其中只有一种数字出现奇数次，其余均出现偶数次，找出出现奇数次的这个数
void FindOne(int nums[], int len, int &x) {
	x = 0;
	for (int i = 0; i < len; i++)
		x ^= nums[i];
}
//设计一个函数，实现：给定一组数字，其中只有两种数字出现奇数次，其余均出现偶数次，找出出现奇数次的这两个数
void FindTwo(int nums[], int len, int &x, int &y) {
	int x_eor_y = 0;
	for (int i = 0; i < len; i++)
		x_eor_y ^= nums[i];
	//提取x_eor_y右数第一个1
	int dif = x_eor_y & (~x_eor_y + 1);
	//初始化x=0
	x = 0;
	for (int i = 0; i < len; i++) {
		if ((nums[i] & dif) != 0)
			x ^= nums[i];
	}
	y = x_eor_y ^ x;
}
int main() {
	int nums1[] = { 2, 1, 1, 3, 4, 3, 4, 2, 2 }; //2出现奇数次
	int len1 = (sizeof(nums1) / sizeof(nums1[0]));
	int test1_x;
	FindOne(nums1,len1,test1_x);
	cout << "test1_x=" << test1_x << endl;
	int nums2[] = { 2, 1, 1, 3, 4, 3, 4, 2, 2, 4 }; //2,4出现奇数次
	int len2 = (sizeof(nums2) / sizeof(nums2[0]));
	int test2_x, test2_y;
	FindTwo(nums2, len2, test2_x, test2_y);
	cout << "test2_x=" << test2_x << ",test2_y=" << test2_y << endl;
}

2.三大排序之冒泡-选择-插入

---

1. 冒泡排序
2. 选择排序
3. 插入排序

---

```c++
#include
using namespace std;
void Swap(int &a, int &b) {
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}
void Print(int *arr,int len){
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
}
//冒泡排序，第1轮比较后，最大的“沉”到最后，它已处在正确的位置，对其之前的元素进行第2轮比较...重复该过程
void BubbleSort(int *arr, int len) {
	int flag;  //优化，如果在某轮比较，全程未发生过交换，那么已经有序
	for (int i = 0; i < len; i++) {
		flag = 0;
		for (int j = 0; j < len - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				Swap(arr[j], arr[j + 1]);
				flag = 1;
			}
		}
		if (flag = 0)
			break;
	}
}
//选择排序，每一轮比较，选出这些元素里的最大（小）值
void SelectSort(int *arr, int len) {
	//先假设第一个是最小值，然后找到真正的最小值与其交换
	int min_id;
	for (int i = 0; i < len; i++) {
		min_id = i;
		for (int j = i+1; j < len; j++) {
			if (arr[j] < arr[min_id])
				min_id = j;
		}
		if(i!=min_id)  //注意，使用Swap不能和自己交换，否则会置为0
			Swap(arr[i], arr[min_id]);
	}
}
//插入排序，从第二个元素开始，正确插入到前面排好序的适当位置
void InsertSort(int *arr, int len) {
	for (int i = 1; i < len; i++) {
		for (int j = i; j > 0; j--) {
			if (arr[j-1] > arr[j])
				Swap(arr[j-1], arr[j]);
		}
	}
}
int main() {
	int test[] = { 5,2,7,1,9,0,3,4 };
	/*BubbleSort(test, 8);
	Print(test, 8);*/
	/*SelectSort(test, 8);
	Print(test, 8);*/
	InsertSort(test, 8);
	Print(test, 8);
}

3.二分法应用扩展

二分法应用前提：序列有序

---

1. 查找某个数

2. 查找>=x的最左侧的数

3. 查找<=x的最右侧的数

4. 找到一个局部最小

---

#include
using namespace std;
//查找某个数，返回其下标
int FindOne(int *arr, int len, int x) {
	int left = 0, right = len - 1;
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] == x)
			return mid;
		else if (arr[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}
//查找>=x的最左边的数
int FindLeftOne(int *arr, int len, int x) {
	int left = 0, right = len - 1;
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] == x) {
			int ans = mid;
			while (left <= mid && arr[--mid] == x) {
				ans = mid;
			}
			return ans;
		}
		else if (arr[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}
//查找<=x的最右边的数
int FindRightOne(int *arr, int len, int x) {
	int left = 0, right = len - 1;
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (arr[mid] == x) {
			int ans = mid;
			while (left <= mid && arr[++mid] == x) {
				ans = mid;
			}
			return ans;
		}
		else if (arr[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}
//找到一个局部最小(已知：len>1,一定存在局部最小)
int FindAreaMin(int *arr, int len) {
	if (arr[0] < arr[1])
		return 0;
	else if (arr[len - 1] < arr[len - 2])
		return len - 1;
	else { //则可得len>3
		int left = 0, right = len - 1;
		int mid;
		while (left <= right) {
			mid = (left + right) / 2;
			if (arr[mid - 1] > arr[mid] && arr[mid] < arr[mid] + 1)
				return mid;
			else if (arr[mid - 1] > arr[mid])
				left = mid + 1;
			else
				right = mid - 1;
		}
	}
}