（2.2.4-6）从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。


不考虑时间复杂度，空间复杂度为o(1)


思路：例SqList L = { 1, 2, 2, 3, 4, 4 },将每一个元素与之后面的元素进行比较，1与2比较不相等不做任何处理，1再次与2比较不做任何处理，1与3比较不做任何处理…1与之后面的所有元素比较不做任何处理；2与2比较，相同第2个2删除即需要将之后的元素向前移动，3需要向前移动1步（即此轮（即内层循环的重复数）遍历的重复次数），后面的两个4需要向前移动1步；后面同理。内层每次比较完应该更新length为length-此轮重复次数。

代码如下：
void Delete_Same(SqList &L){
	//删除有序表重复值
	
	for(int i=0;i<L.length;i++)
	{
		int same=0;
		for(int j=i+1;j<L.length;j++){
			if (L.data[i] == L.data[j])
			{
				same++;
			}	
			else{
				L.data[j-same]=L.data[j];
			}
		}
		L.length=L.length-same;
	}
}



时间复杂度为o(n)，空间复杂度为o(1)


思路（转自https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-yuan-su-y/）:

使用快慢双指针法 分别定义指针i与指针j，开始两指针都指向num[0],

快指针i向前移动 指向的数组与 慢指针j所知数组比较 num【j】！=num【i】

若相同则快指针向前移动一格，慢指针向前移动一格；若不同，将快指针i指向数组赋值给慢指针j，快慢指针分别向前移动一格；重复操作直到i指针指到末尾。

若数组长度为0则直接return 0；

最后 返回慢指针所指数组长度加一 return j+1。
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i,j;
        int length=nums.size();
       
        if(length==0)//判断数组长度  若为0直接返回
        return 0;

        for (i=0;i<nums.size();i++)//采用for循环使指针i不停向前移动
    {
        if(nums[i]!=nums[j])
      {
        if(i-j>1) //判断快慢指针 若相邻数组且元素值不同时，虽然也可进行赋值操作，
                  //但可以省略该赋值操作，避免无意义操作提高运行效率
        {nums[j+1]=nums[i];}
          j++;
      }  
       
     }

 return j+1;

    }
};

插入元素
如在一个递增和排列数组a中插入一个数x，使其仍然有序

思路：

查找应该放置的位置k
从最后一个数开始直到第k个元素为止，每一个元素下标向后移动一个位置
将x插入k位置

步骤2要从最后一个元素开始移动

for(i = n - 1 ; i > = k ; i - - )

a[ i + 1] = a [ i ]
代码实现
#define N 10
#include <iostream>
using namespace std;

int main()
{
	int a[N], i, k, n, x;
	cout << "递增输入现有的元素个数：";
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	cout << "要插入的元素：";
	cin >> x;
	for (i = 0; i < n; i++)
		if (x < a[i])
			break;
	k = i;
	for (i = n - 1; i >= k; i--)
		a[i + 1] = a[i];
	a[k] = x;
	for (i = 0; i < n + 1; i++)
		cout << a[i] << " ";
	return 0;
}


删除元素
思路：

找到该元素的位置k
找到后删除，然后从第k+1位依次向前移
若没找到提示“未找到”

代码实现
#define N 10
#include <iostream>
using namespace std;

int main()
{
	int a[N], i, k, x, n;
	cout << "输入现有数组中元素的个数为：";
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	cout << "输入要删除的数为：";
	cin >> x;
	for (i = 0; i < n; i++)
		if (x == a[i])
			break;
	k = i;
	for (i = k; i < n; i++)
		a[i] = a[i + 1];
	for (i = 0; i < n - 1; i++)
		cout << a[i] << " ";
}

本学期带数据结构，那就索性复习下C语言，把所写的代码记录下来
题目如下：
1.	两个有序的顺序表A和B，包含的元素个数分别为m与n，设计一算法实现B=AUB
2.	设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变
3.	设计一高效算法删除顺序表中值为x的所有元素

代码如下：
</pre><pre class="cpp" name="code">写惯了JAVA，Python，要注意C语言没法动态构建数组，必须先申请数组空间，其次声明要写在最前面。
#include <stdio.h>
#include <stdlib.h>

#define len 100			//数组长度
#define endflag -99		//结束标记

//获得数组，返回长度
int getArray(int *p){
	int length =0;
	int i = 0;
	for(scanf("%d",&i);i!=endflag;scanf("%d",&i))
    {
		*p++ = i;
        length++;
    }
    return length;
}

//输出数组
void printArray(int *p, int length){
	int i;
	printf("数组：");
    for(i=0;i<length;i++)
		printf("%d  ",*(p+i));
    printf("\n");
}

//有序数组的并集
int ArrayUnion(int *a,int A_len,int *b,int B_len,int *out){
	int *p,pLen,aLen,bLen;
    p = out;
	pLen = aLen = bLen = 0;

    while(aLen != A_len && bLen != B_len){
            
		if(aLen < A_len && bLen < B_len){
			if(*a > *b){
				 *p = *b;
				 b++;bLen++;
			}else if(*a == *b){
				*p = *b;
				a++;b++;
				aLen++;bLen++;
			}else{
				*p = *a;
				a++;aLen++;
			}
			p++;pLen++;
		}
        
        if(aLen<A_len && bLen == B_len){
				*p = *a;
				a++;aLen++;
				p++;pLen++;
        }
		
        if(aLen==A_len && bLen < B_len){
				*p = *b;
				 b++;bLen++;
				 p++;pLen++;
        }
		
    }
    
    return pLen;
}

// 删除数组的第k个元素
int ArrayDelElem(int *arr,int length,int k){
	int i;

	if(k>length) return 0;

	for(i=k;i<length;i++){
		arr[i] = arr[i+1];
	}
	return length - 1 ;
}

//删除数组中的j-k个元素
int ArrayDelRange(int *arr,int length,int j,int k){
	int i,range;
	range = k-j;

	if(k>length) return 0;

	for(i=j;i<length - range;i++){
		arr[i] = arr[i+range+1];
	}
	return length - range - 1 ;
}

//顺序表去重复，返回数组长度
int distinct(int *arr,int length){
	int i,k,reLen;
	k = 1;					//去除元素的个数
	reLen = length;

	for(i=0;i<length - k ;i++){
		if(arr[i] == arr[i+1]){
			reLen = ArrayDelElem(arr,reLen,i+1);
			k++;
			i--;  //抵消++的作用，从这个数继续往下比
		}
	}
	return reLen;
}

//删除顺序表中所有值为X的元素
int ArrayDelX(int *arr,int length,int x){
	int i,PreIndex,AfterIndex;

	for(i=1;i<length;i++){
		if(arr[i-1] < x){
			if(arr[i] == x) PreIndex = i;
		}else if(arr[i-1] == x){
			if(arr[i] > x){
				AfterIndex = i-1;
				break;
			}
		}
	}

	return ArrayDelRange(arr,length,PreIndex,AfterIndex);
}

int main()
{

    int A[len],A_len; 

    printf("请输入数组A，输入%d结束：\n",endflag);
    A_len = getArray(A);
    //A_len = distinct(A,A_len);  	//第二题
    A_len = ArrayDelX(A,A_len,2);   //第三题
    printArray(A,A_len);

	/*//第一题
    int *out,k[2*len],A_len,B_len,outlen;
    int A[len],B[len]; 
    out = k;

    printf("请输入数组A，输入%d结束：\n",endflag);
    A_len = getArray(A);
    printf("请输入数组B，输入%d结束：\n",endflag);
    B_len = getArray(B);
    
    outlen = ArrayUnion(A,A_len,B,B_len,out);
    printArray(out,outlen);
	*/

    return 0;
}








归并排序是一个对递归和分治很好诠释的一个排序算法
它是将一个无序的数组依次分开使之变为有序的数组，如果我们一直将其分解到一个数组中只有一个数，那么我们就可以理解为他是有序的，然后再将这些有序的数组依次合并成一个数组，至于如何合并就很简单了，我们只需要比较第一个数字，哪个数组的数字大就选取哪个数组的，然后把第一个数字拿到新的数组中，然后删除原数组中的值，依次比较，如果其中一个数组空了，那么我们就将另一个数组全部拿到新数组中，这样我们就可以得到一个有序的新数组，依次合并最终完成排序，举一个例子就很好理解。
（23，12，5，76，32，87，34，11）这里他是一个无序的数组，我们先把他进行分解
 （23，12，5，76）(32，87，34，11）--->（23，12) (5，76）（32，87) (34，11）
   (23)(12)(5)(76)(32)(87)(34)(11)此时出现的8个数组都可以视为有序的
    然后依次进行合并
    （12，23）（5，76）（32，87）（11，34）-->（5，12，23，76）（11，32，34，87）
   最终变为（5，11，12，23，32，34，76，87）完成排序
代码如下
public class MergeSort {

    public static void merge(int[] a, int low, int mid, int high) {
        int i = low;// 定义左指针
        int j = mid + 1;// 定义右指针
        int k = 0;
      int[] temp = new int[high - low + 1]；
      while (i <= mid && j <= high) {
          if (a[i] < a[j]) { 
            temp[k++] = a[i++]; 
          }
        else { 
          temp[k++] = a[j++]; 
         }
     } // 把左边剩余的数移入数组 
    while (i <= mid) { 
        temp[k++] = a[i++];  
    } // 把右边边剩余的数移入数组 
    while (j <= high) { 
           temp[k++] = a[j++];
      } // 把新数组中的数覆盖nums数组 
for (int k2 = 0; k2 < temp.length; k2++) {
     a[k2 + low] = temp[k2]; 
  } 
}
 public static void mergeSort(int[] a, int low, int high) {
            int mid = (low + high) / 2; 
            if (low < high) {
                 // 对左边进行分解 mergeSort(a, low, mid);
                 // 对右边进行分解 mergeSort(a, mid + 1, high); 
                 // 左右进行归并 merge(a, low, mid, high); 
                  System.out.println(Arrays.toString(a)); 
               } 
  }
   public static void main(String[] args) { 
          int a[] = { 23，12，5，76，32，87，34，11}; 
          mergeSort(a, 0, a.length - 1);
           System.out.println("排序结果：" + Arrays.toString(a)); }
}