DataStructures_WD_408_Qeustion_Array

数组

代码

点我查看

综合应用第一题

点我查看

#include<iostream>
#include<vector>
using namespace std;
bool deleteMinVal(vector<int>& array, int& val){
	if(array.size()==0)return false;
	int p=0;
	val=array[0];
	for(int i=1;i<array.size();i++){
		if(array[i]<val){
			p=i;
			val=array[i];
		}
	}
	array[p]=array[array.size()-1];
	array.pop_back();
	return true;
}
int main(){
	vector<int> a={2,1,4,5,3};
	int val;
	while(deleteMinVal(a, val)){
		cout<<"删除的最小元素为: "<<val<<endl;
	}
	return 0;
}

综合应用第二题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void reverseArray(vector<int>& array){
	int t;
	for(int i=0;i<array.size()/2;i++){
		t=array[i];
		array[i]=array[array.size()-1-i];
		array[array.size()-1-i]=t;
	}
}
int main(){
	vector<int> a={2,1,4,5,3};
	reverseArray(a);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第三题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void removeAllSpecifiedElements(vector<int>& array, int x){
	int t=0;
	for(int i=0;i<array.size();i++){
		if(array[i] == x){
			t++;
			continue;
		}
		array[i-t]=array[i];
	}
	while(t--)array.pop_back();
}
int main(){
	vector<int> a={2,3,1,3,4,5,3};
	removeAllSpecifiedElements(a, 3);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第四题

点我查看

#include<iostream>
#include<vector>
using namespace std;
bool removeBetweenSAndTElement(vector<int>& array, int s, int t){
	if(s>=t || array.empty())return false;
	int i=0,j=0;
	while(i<array.size()){
		if(array[i]>s && array[i]<t)j++;
		else if(array[i]>=t)break;
		i++;
	}
	if(t==0)return true;
	for(;i<array.size();i++){
		array[i-j]=array[i];
	}
	while(j--)array.pop_back();
	return true;
}
int main(){
	vector<int> a={1,2,3,4,5,6,7,8,9};
	removeBetweenSAndTElement(a, 3, 7);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第五题

点我查看

#include<iostream>
#include<vector>
using namespace std;
bool removeBetweenSAndTElement(vector<int>& array, int s, int t){
	if(s>=t || array.empty())return false;
	int i=0,j=0;
	while(i<array.size()){
		if(array[i]>=s && array[i]<=t)j++;
		else if(array[i]>t)break;
		i++;
	}
	if(t==0)return true;
	for(;i<array.size();i++){
		array[i-j]=array[i];
	}
	while(j--)array.pop_back();
	return true;
}
int main(){
	vector<int> a={1,2,3,4,5,6,7,8,9};
	removeBetweenSAndTElement(a, 3, 7);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第六题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void removeSameElement(vector<int>& array){
	if(array.empty())return;
	int t=0;
	for(int i=1;i<array.size();i++){
		if(array[i]==array[i-1]){
			t++;
			continue;
		}
		array[i-t]=array[i];
	}
	while(t--){
		array.pop_back();
	}
}
int main(){
	vector<int> a={1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,9};
	removeSameElement(a);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第七题

点我查看

#include<iostream>
#include<vector>
using namespace std;
vector<int> merge(vector<int> nums1, int m, vector<int> nums2, int n) {
	int i = m + n -1;
	m--, n--;
	vector<int> reNums(i+1);
	while(m>=0&&n>=0){
		if(nums1[m]<nums2[n]){
			reNums[i]=nums2[n--];
		} else {
			reNums[i]=nums1[m--];
		}
		i--;
	}
	if(n>=0){
		for(i=0;i<=n;i++) reNums[i] = nums2[i];
	}
	if(m>=0){
		for(i=0;i<=m;i++) reNums[i] = nums1[i];
	}
	return reNums;
}
int main(){
	vector<int> a={4,5,6,7,8,9},b={1,2,3,4,5,6,7,8,9};
	a = merge(a, 6, b ,9);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第八题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void reverseArray_m_Array_n(vector<int>& nums, int m, int n) {
	int t;
	for(int i=0;i<m/2;i++){
		t=nums[i];
		nums[i]=nums[m-1-i];
		nums[m-1-i]=t;
	}
	for(int i=0;i<n/2;i++){
		t=nums[m+i];
		nums[m+i]=nums[n+m-1-i];
		nums[n+m-1-i]=t;
	}
	for(int i=0;i<(m+n)/2;i++){
		t=nums[i];
		nums[i]=nums[m+n-1-i];
		nums[m+n-1-i]=t;
	}
}
int main(){
	vector<int> a={1,2,3,4,5,6,7,8,9,10};
	reverseArray_m_Array_n(a, 5, 5);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用题第九题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void FindElement(vector<int>& array,int x){
	int l=-1,r=array.size();
	int t;
	while(l+1!=r){
		t=(l+r)/2;
		if(array[t]>=x)r=t;
		else l=t;
	}
	if(r==array.size()){
		array.push_back(x);
	}else if(array[r]!=x){
		for(int i=r;i<array.size();i++){
			t=array[i];
			array[i]=x;
			x=t;
		}
		array.push_back(x);
	}else{
		if(r+1!=array.size()){
			t=array[r];
			array[r]=array[r+1];
			array[r+1]=t;
		}
	}
}
int main(){
	vector<int> a={1,2,3,4,5,6,7,8,9,10};
	FindElement(a, 11);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第十题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void leftShiftP(vector<int>& nums, int m) {
	int t;
    int n=nums.size()-m;
	for(int i=0;i<m/2;i++){
		t=nums[i];
		nums[i]=nums[m-1-i];
		nums[m-1-i]=t;
	}
	for(int i=0;i<n/2;i++){
		t=nums[m+i];
		nums[m+i]=nums[n+m-1-i];
		nums[n+m-1-i]=t;
	}
	for(int i=0;i<(m+n)/2;i++){
		t=nums[i];
		nums[i]=nums[m+n-1-i];
		nums[m+n-1-i]=t;
	}
}
int main(){
	vector<int> a={1,2,3,4,5,6,7,8,9,10};
	leftShiftP(a, 4);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第十题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void leftShiftP(vector<int>& nums, int m) {
	int t;
    int n=nums.size()-m;
	for(int i=0;i<m/2;i++){
		t=nums[i];
		nums[i]=nums[m-1-i];
		nums[m-1-i]=t;
	}
	for(int i=0;i<n/2;i++){
		t=nums[m+i];
		nums[m+i]=nums[n+m-1-i];
		nums[n+m-1-i]=t;
	}
	for(int i=0;i<(m+n)/2;i++){
		t=nums[i];
		nums[i]=nums[m+n-1-i];
		nums[m+n-1-i]=t;
	}
}
int main(){
	vector<int> a={1,2,3,4,5,6,7,8,9,10};
	leftShiftP(a, 4);
	for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第十一题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void findMiddle(vector<int> nums1,vector<int> nums2,int& val){
	int i=0,j=0;
	while(1){
		if(i+j == nums1.size()-1){
			val=min(nums1[i], nums2[j]);
			return;
		}
		if(nums1[i]>nums2[j]){
			j++;
		}
		else {
			i++;
		}
	}
}
int main(){
	vector<int> a={1,3,6,7,9,11},b={1,3,4,7,8,10};
	int val;
	findMiddle(a, b, val);
	// for(auto i: a)cout<<i<<" ";
	cout<<val;
	return 0;
}

综合应用第十二题

点我查看

#include<iostream>
#include<vector>
using namespace std;
void findMainElement(vector<int> nums, int& val){
	int s=0;
	for(auto i:nums){
		if(s==0){
			val=i;
			s++;
		}
		else if(i==val)s++;
		else s--;
	}
	if(s){
		s=0;
		for(auto i:nums){
			if(i==val)s++;
		}
		if(s<=nums.size()/2)val=-1;
	}else val=-1;
}
int main(){
	vector<int> a={11,11,11,13,13,13,11};
	int val;
	findMainElement(a, val);
	// for(auto i: a)cout<<i<<" ";
	cout<<val;
	return 0;
}

综合应用第十三题

点我查看

#include<iostream>
#include<vector>
using namespace std;
int findMinAbsentElement(vector<int> nums){
	for(int i=0;i<nums.size();i++){
		if(nums[i]<=0)nums[i]=int(nums.size()+1);
	}
	for(int i=0;i<nums.size();i++){
		if(abs(nums[i])<=nums.size()) nums[abs(nums[i])-1] = -1 * abs(nums[abs(nums[i])-1]);
	}
	for(int i=0;i<nums.size();i++){
		if(nums[i]>0)return i+1;
	}
	return int(nums.size()+1);
}
int main(){
	vector<int> a={-5,3,2,3};
	cout<<findMinAbsentElement(a);
	// for(auto i: a)cout<<i<<" ";
	return 0;
}

综合应用第十四题

点我查看

#include<iostream>
#include<vector>
using namespace std;
int dis(int a,int b, int c){
	return abs(a-b)+abs(c-b)+abs(a-c);
}
int findMinDistanceTriplet(vector<int> nums1,vector<int> nums2,vector<int> nums3){
	int i=0,j=0,k=0;
	int ans=0x3f3f3f3f;
	while(i<nums1.size() && j<nums2.size() && k<nums3.size()){
		ans=min(ans,dis(nums1[i],nums2[j],nums3[k]));
		if(nums1[i]<=nums2[j] && nums1[i]<=nums3[k])i++;
		else if(nums2[j]<=nums1[i] && nums2[j]<=nums3[k])j++;
		else k++;
	}
	return ans;
}
int main(){
	vector<int> a={-1,0,9},b={-25,-10,10,11},c={2,9,17,30,41};
	cout<<findMinDistanceTriplet(a,b,c);
	// for(auto i: a)cout<<i<<" ";
	return 0;
}