参考教材: 《2021年王道数据结构复习指导》

$2.2$ 顺序表

  • 采用$C$++$11$完成习题
  • 一般情况下，顺序表的数据类型采用$\textrm{int}$
  • $\textrm{print(int *a,int n)}$函数用于打印顺序表
  • $\textrm{swap(type &a,type &b)}$函数用于交换两个元素的值
  • 测试结果将写在注释部分
  • 源代码下载
Get it!Download

$0$.程序框架

#include <iostream>
using namespace std;
void print(int *a,int n)
{
	for(int i = 0;i < n;i++)
		cout<<a[i]<<(i==n-1?"\n":" ");
}
/*
* 镶嵌函数和测试代码
*/
int main(void)
{
	//test_chapter2_array_1();
	//test_chapter2_array_2();
	//test_chapter2_array_3();
	//test_chapter2_array_4();
	//test_chapter2_array_5();
	//test_chapter2_array_6();
	//test_chapter2_array_7();
	//test_chapter2_array_8();
	//test_chapter2_array_9();
	//test_chapter2_array_10();
	//test_chapter2_array_11();
	//test_chapter2_array_12();
	//test_chapter2_array_13();
	return 0;
}

$1$. 删除顺序表中的最小元素(假设唯一)并返回该元素，将后续元素前移来填充该空位，若表空则报错并退出。

bool problem_chapter2_array_1(int *a,int &size,int &val)
{
	if(size == 0) return false;
	int min_index = 0;
	for(int i = 1;i < size;i++) 
		if(a[i] < a[min_index]) 
			min_index = i;
	val = a[min_index];
	for(int i = min_index;i < size-1;i++)
		a[i] = a[i+1];
	size--;
	return true;
}	

void test_chapter2_array_1()
{
	int a[8] = {8,2,6,5,1,4,3,9};
	int size = 8;
	int val;
	
	print(a,size);
	if(problem_chapter2_array_1(a,size,val))
	{
		cout<<"min value:"<<val<<endl;
		print(a,size);
	} 
}

/*
* Test Chapter2 Array 1 Result:
* 8 2 6 5 1 4 3 9
* min value:1
* 8 2 6 5 4 3 9
*/

$2$.设计一个高效算法逆置顺序表内的所有元素，要求空间复杂度为$O(1)$。

void problem_chapter2_array_2(int *a,int size)
{
	for(int i = 0;i < (size>>1);i++)
		swap(a[i],a[size-i-1]);
}

void test_chapter2_array_2()
{
	int a[8] = {1,2,3,4,5,6,7,8};
	int size = 8;
	
	print(a,size);
	problem_chapter2_array_2(a,size);
	print(a,size);
}

/*
* Test Chapter2 Array 2 Result:
* 1 2 3 4 5 6 7 8
* 8 7 6 5 4 3 2 1
*/

$3$.对长度为$n$的顺序表，编写一个时间复杂度度为$O(n)$，空间复杂度为$O(1)$的算法，删除线性表中所有值为$x$的元素。

void problem_chapter2_array_3(int *a,int &n,int x)
{
	int index = 0;
	for(int i = 0;i < n;i++)
		if(a[i] != x)
			a[index++] = a[i];
	n = index;
}

void test_chapter2_array_3()
{
	int a[9] = {1,2,1,3,1,4,1,1,5};
	int size = 9;
	
	print(a,size);
	problem_chapter2_array_3(a,size,1);
	print(a,size);
}
/*
* Test Chapter2 Array 3 Result:
* 1 2 1 3 1 4 1 1 5
* 2 3 4 5
*/

$4$.从有序顺序表中删除在给定$s$和$t$之间的所有元素(包括$s,t$)，如果$s,t$不合理或者表空，则报错并退出。

bool problem_chapter2_array_4(int *a,int &n,int s,int t)
{
	if(s >= t || !n) return false;
	int index = 0;
	for(int i = 0;i < n;i++)
		if(a[i] < s || a[i] > t)
			a[index++] = a[i];
	n = index;
}

void test_chapter2_array_4()
{
	int a[9] = {1,2,3,4,5,6,7,8,9};
	int size = 9;
	
	print(a,size);
	problem_chapter2_array_4(a,size,3,6);
	print(a,size);
}

/*
* Test Chapter2 Array 4 Result:
* 1 2 3 4 5 6 7 8 9
* 1 2 7 8 9
*/

$5$.从顺序表(和4相比，不再有序)中删除在给定$s$和$t$之间的所有元素(包括$s,t$)，如果$s,t$不合理或者表空，则报错并退出。

bool problem_chapter2_array_5(int *a,int &n,int s,int t)
{
	if(s >= t || !n) return false;
	int index = 0;
	for(int i = 0;i < n;i++)
		if(a[i] < s || a[i] > t)
			a[index++] = a[i];
	n = index;
}

void test_chapter2_array_5()
{
	int a[9] = {3,1,5,7,9,2,4,6,8};
	int size = 9;
	
	print(a,size);
	problem_chapter2_array_5(a,size,3,6);
	print(a,size);
}

/*
* Test Chapter2 Array 5 Result:
* 3 1 5 7 9 2 4 6 8
* 1 7 9 2 8
*/

$6$.从有序顺序表中删除所有其值重复的元素，使表中的所有元素的值均不同。

void problem_chapter2_array_6(int *a,int &size)
{
	int index = 1;
	for(int i = 1;i < size;i++)
		if(a[i] != a[i-1])
			a[index++] = a[i];
	size = index;
}

void test_chapter2_array_6()
{
	int a[10] = {1,2,2,3,3,3,4,4,4,4};
	int size = 10;
	
	print(a,size);
	problem_chapter2_array_6(a,size);
	print(a,size);
}

/*
* Test Chapter2 Array 6 Result:
* 1 2 2 3 3 3 4 4 4 4
* 1 2 3 4
*/

$7$.将两个有序顺序表合并成一个新的有序表，并由函数返回结果顺序表。

int* problem_chapter2_array_7(int *a,int n,int *b,int m,int& size)
{
	size = n+m;
	int *c = new int [size];
	int i = 0,j = 0,k = 0;
	while(i < n && j < m)
	{
		if(b[j] < a[i]) c[k++] = b[j++];
		else c[k++] = a[i++];
	}
	while(i < n) c[k++] = a[i++];
	while(j < m) c[k++] = b[j++];
	return c;
}

void test_chapter2_array_7()
{
	int a[] = {1,3,5,7,9};
	int b[] = {2,4,6,8};
	int size = 0;
	int *c = problem_chapter2_array_7(a,5,b,4,size);
	print(c,size);
	
}

/*
* Test Chapter2 Array 7 Result:
* 1 2 3 4 5 6 7 8 9
*/

$8$.已知在一维数组中$A[m+n]$中依次存放两个线性表$(a_1,a_2,a_3, …… ,a_m)$和$(b_1,b_2,b_3, …… ,b_n)$,试编写一个函数，将数组中两个顺序表的位置互换，变为$(b_1,b_2,b_3, …… ,b_n)$和$(a_1,a_2,a_3, …… ,a_m)$。

void reverse(int *a,int begin,int end)
{
	for(int i = begin;i < (end+begin)/2;i++)
		swap(a[i],a[end+begin-i-1]);
}

void problem_chapter2_array_8(int *a,int m,int n)
{
	reverse(a,0,m+n);
	reverse(a,0,n);
	reverse(a,n,m+n);
}

void test_chapter2_array_8()
{
	int a[10] = {1,2,3,4,1,2,3,4,5,6};
	int size = 10;
	
	print(a,size);
	problem_chapter2_array_8(a,4,6);
	print(a,size);
}

/*
* Test Chapter2 Array 8 Result:
* 1 2 3 4 1 2 3 4 5 6
* 1 2 3 4 5 6 1 2 3 4
*/

$9$.在有序顺序表内查找值为$x$的元素，并将其与其后继元素交换，若找不到则将其插入表中使表仍然有序。

void problem_chapter2_array_9(int *a,int &size,int x)
{
	int left = 0,right = size-1,mid;
	while(left <= right)
	{
		mid = (left+right)>>1;
		if(a[mid] < x) left = mid+1;
		else if(a[mid] > x)right = mid-1;
		else break;
	}
	if(a[mid] == x && mid != size-1) swap(a[mid],a[mid+1]); 
	else if(left > right)
	{
		for(int i = size-1;i > right;i--)
			a[i+1] = a[i];
		a[right+1] = x;
		size++;
	}
}

void test_chapter2_array_9()
{
	int a[10] = {1,2,3,4,6,7,8,9};
	int size = 8;
	
	print(a,size);
	problem_chapter2_array_9(a,size,5);
	//problem_chapter2_array_9(a,size,7);
	print(a,size);
}

/*
* Test Chapter2 Array 9 Result:
* 1 2 3 4 6 7 8 9
* x = 5
* 1 2 3 4 5 6 8 7 9

* 1 2 3 4 6 7 8 9
* x = 7
* 1 2 3 4 6 8 7 9
*/

$10$.数组$a$中存放有$n$个元素，设计一个时间和空间两方面都尽可能高效的算法，将$a$中保存的序列循环左移$p(0<p<n)$个位置，即把$(a_0,a_1,a_2, …… ,a_{n-1})$变换为$(a_p,a_{p+1},……,a_{n-1},a_0,a_1, …… ,a_{p-1})$，说明你设计的时间复杂度和空间复杂度。

//调用第8题撰写的reverse函数 
void problem_chapter2_array_10(int *a,int size,int p)
{
	reverse(a,0,size);
	reverse(a,0,size-p);
	reverse(a,size-p,size);
}

void test_chapter2_array_10()
{
	int a[10] = {1,2,3,4,1,2,3,4,5,6};
	int size = 10;
	
	print(a,size);
	problem_chapter2_array_10(a,10,4);
	print(a,size);
}

/*
* Test Chapter2 Array 10 Result:
* 1 2 3 4 1 2 3 4 5 6
* 1 2 3 4 5 6 1 2 3 4
*/

时间复杂度: $O(n)$

空间复杂度: $O(1)$

$11$.定义中位数是第$\textrm{(int)n/2}$个元素，现给出两个等长有序的数组，找出他们合并的中位数，说明你设计的时间复杂度和空间复杂度。

int problem_chapter2_array_11(int *a,int *b,int n)
{
	int left1 = 0,right1 = n-1,left2 = 0,right2 = n-1,mid1,mid2;
	while(left1 != right1 || left2 != right2)
	{
		mid1 = (left1+right1)/2;
		mid2 = (left2+right2)/2;
		if(a[mid1] == b[mid2]) return a[mid1];
		if(a[mid1] < b[mid2])
		{
			if(!((left1+right1)&1))
			{
				left1 = mid1;
				right2 = mid2;
			}
			else
			{
				left1 = mid1+1;
				right2 = mid2;
			}
		}
		else
		{
			if(!((left2+right2)&1))
			{
				right1 = mid1;
				left2 = mid2;
			}
			else
			{
				right1 = mid1;
				left2 = mid2+1;
			}
		}
	}
	return a[left1] < b[left2]?a[left1]:b[left2];
}

void test_chapter2_array_11()
{
	int a[5] = {11,13,15,17,19};
	int b[5] = {2,4,6,8,20};
	int n = 5;
	cout<<problem_chapter2_array_11(a,b,5)<<endl;
}

/*
* Test Chapter2 Array 11 Result:
* 11
*/

时间复杂度: $O(\log_2n)$

空间复杂度: $O(1)$

$12$.定义主元素：存在个数超过数组长度一半的元素，搜索一个数组是否存在主元素，是则返回该元素，否则返回-$\textrm{1}$。

本题采用了$BM$投票算法，详情可以参考文章$\textrm{Boyer-Moore}$投票算法

Boyer-Moore投票算法
2021-3-31 0 
int problem_chapter2_array_12(int *a,int size)
{
    int val = -1;     
    int count = 0;    
    for (int i = 0;i < size;i++) 
    {
        if (a[i] == val) count++;
        else
        {
            count--;
            if(count < 0)
            {
                val = a[i];
                count = 1;
            }
        }
    }
    return (count>0)?val:-1;
}

void test_chapter2_array_12()
{
	int a[8] = {0,5,5,3,5,7,5,5};
	int b[8] = {0,5,5,3,5,1,5,7};
	cout<<problem_chapter2_array_12(a,8)<<endl;
	cout<<problem_chapter2_array_12(b,8)<<endl;
}

/*
* Test Chapter2 Array 12 Result:
* 5
* -1
*/

时间复杂度: $O(n)$

空间复杂度: $O(1)$

$13$.寻找一个数组没出现的最小正数，例如$\{-5,3,2,3\}$返回$1$，$\{1,2,3\}$返回$4$。说明你设计的时间复杂度和空间复杂度。

int problem_chapter2_array_13(int *a,int size)
{
	bool *vis = new bool [size+1]();
	for(int i = 0;i < size;i++) 
		if(a[i] > 0) 
			vis[a[i]] = true;
			
	for(int i = 1;i <= size;i++)
		if(!vis[i])
			return i;
	return size+1;
}

void test_chapter2_array_13()
{
	int a[4] = {-5,3,2,3};
	int b[3] = {1,2,3};
	cout<<problem_chapter2_array_13(a,4)<<endl;
	cout<<problem_chapter2_array_13(b,3)<<endl;
}

/*
* Test Chapter2 Array 13 Result:
* 1
* 4
*/

时间复杂度: $O(n)$

空间复杂度: $O(n)$

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2021-04-03 15:30}$