算法学习

三天学习完数组相关内容并总结
使用语言：C#
使用编译器：Visual Studio

• 1.数组二分查找
• 2.数组移除指定元素
• 3.有序数组平方

• 数组二分查找

输入：有序数组
产出：在数组中找到返回指定数值在数组中的位置下标，没找到返回-1
要求：使用二分查找

public static int dichotomy()
        {
            int[] arr = new int[] { 2, 5, 9, 12, 19, 23, 67, 90 };
            int target = 67;
            //定义左右变量标记区间位置
            int left = 0;
            int right = arr.Length-1;
            while (right >= left)
            {
                int middle = (right - left) / 2 + left;
                //从中间开始比较
                if (target == arr[middle])
                {
                    return middle;
                }
                else if (target > arr[middle])//要找的数比中间值大，区间规定为m-r  中间值已经比较过
                {
                    left = middle + 1;
                }
                else//要找的数比中间值小，区间规定为l-m  中间值已经比较过
                {
                    right = middle - 1;
                }
            }
            return -1;
        }

• 数组移除指定元素

输入：数组nums，值val
产出：移除后的数组
要求：不使用额外数组空间

双循环的时间复杂度为n的平方，双指针的时间复杂度为n

public static void deleteItems(int val)
        {
            int[] nums =new int[] { 2, 5, 9, 12, 19, 23, 67, 90 };
            //int size = nums.Length;
            //@1双循环
            //for(int i = 0; i < size; i++)
            //{
            //    if (nums[i] == val)
            //    {
            //        for(int j = i+1; j < size; j++)//(i+1)后的元素都往前移一个位置
            //        {
            //            nums[j - 1] = nums[j];
            //        }
            //        i--;//元素前移，i计数也对应前移
            //        size--;//同i
            //    }
            //}
            //for (int i = 0; i < size; i++)
            //{
            //    Console.WriteLine(nums[i]);
            //}

            //@2双指针  fast快指针循环遍历原数组   slow慢指针记录去除指定数值后的数组   
            int slow = 0;int fast = 0;
            for(fast = 0; fast < nums.Length; fast++)
            {
                if (nums[fast] != val)//循环遇到指定数值的时候，slow不做改变
                {
                    nums[slow] = nums[fast];
                    slow++;
                }
            }
            for(int i = 0; i < slow; i++)
            {
                Console.WriteLine(nums[i]);
            }
        }

• 有序数组平方

输入：有序数组
产出：数组平方后有序输出

从两端往中间比较，两端中的其中一个一定是最大的

public static void squareOr()
        {
            int[] nums = new int[] { -12, -9, -4, 2, 4, 7, 9, 11 };
            int left = 0;
            int right = nums.Length - 1;
            int[] target = new int[nums.Length];//声明新数组保存比较后的结果，防止数据污染
            for(int i = nums.Length-1; i >=0; i--)//从后往前，两个末端较大的放最后
            {
                if (nums[left] * nums[left] >= nums[right] * nums[right])
                {
                    target[i] = nums[left] * nums[left];
                    left++;
                }
                else
                {
                    target[i] = nums[right] * nums[right];
                    right--;
                }
            }
            for(int i = 0; i < nums.Length; i++)
            {
                Console.WriteLine(target[i]);
            }
        }