天勤2022数据结构（一）线性表

设将n（n>1）个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效的算法。将R中保存的序列循环左移P（0<P<n）个位置，即将R中的数据由（X₀，X₁，…，X_n-1）变换为（X_p，X_p+1，…，X_n-1，X₀，X₁，…，X_p-1）。要求

（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法关键之处给出注释。
（3）说明你所设计的算法的时间复杂度和空间复杂度。

---

基本设计思想:

1. 将R中前P个元素逆置
2. 将剩下的元素逆置
3. 将R中所有的元素整体逆置

---

void swap(int[] R, int i, int j){
	R[i] = R[i]^R[j];
	R[j] = R[i]^R[j];
	R[i] = R[i]^R[j];
}

void reverse(int[] R, int i, int j){
	for(; i<j; i++, j--){
		swap(R, i, j);
	}
}

void solution(int[] R, int n, int p){
	reverse(0, p-1);
	reverse(p, n-1);
	reverse(0, n-1);
}

---

时间复杂度:O(n)
空间复杂度:O(1)

3. 已知一个整数序列A=（a₀，a₁，…，a_n-1），其中0≤a_i<n（0≤i<n）若存在a_p1=a_p2=…=a_pm=x且m>n/2（0≤p_k≤n, 1≤k≤m），则称x为A的主元素，例如，A=（0，5，5，3，5，7，5, 5), 则5为主元素；又如，A=（0，5，5，3，5，1，5，7），则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素;否则输出-1。要求：

（1）给出算法的基本设计思想
（2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释
（3）说明你所设计算法的时间复杂度和空间复杂度

---

基本设计思想:
从前往后扫描数组元素,标记出一个可能成为主元素的元素num, 然后重新计数,确认num是否是主元素

1. 选取候选的主元素，依次扫描所给数组中的每个整数，用cnt记录num的出现次数，将第一个遇到的整数num保存到ans中，cnt=1
2. 若遇到的下一个整数仍等于num，则cnt+=1，否则cnt-=1
3. 当cnt减到0时，将遇到的下一个整数保存到ans中，cnt重新赋值1，开启新一轮计数，即从当前位置开始重复上述过程，直至扫描完全部数组元素
4. 判断ans中元素是否时真正的主元素。再次扫描该数组，统计ans中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素

---

算法实现：

int majority(int A[], int n){
	int ans, cnt;
	ans = A[0];
	for(int i=1; i<n; i++){
		if(A[i] == ans){
			cnt++;
		}else{
			if(cnt > 0){
				cnt--;
			}else{
				ans = A[i];
				cnt = 1;
			}
		}
	}
	if(cnt > 0){
		for(i = cnt = 0; i<n; i++){
			if(A[i] == ans)
				cnt++;
		}
	}
	return cnt>n/2? ans: -1;
}

---

时间复杂度：O(n)
空间复杂度：O(1)