算法之双指针法(一)

Near_Li 发布于2019-08-16 11:12 / 850人阅读

摘要：双指针法在很多场景及算法中都有使用主要应用的算法题如下一个数组中有奇数也有偶数，将所有奇数放到数组左边，将所有偶数放到数组右边奇数偶数时间复杂度一个数组中既有奇数也有偶数，奇数的下标是奇数，偶数的下标是偶数偶数奇数如果数组最后一个是

   双指针法在很多场景及算法中都有使用
   主要应用的算法题如下：

一个数组中有奇数也有偶数，将所有奇数放到数组左边，将所有偶数放到数组右边

int[] array = {2, 1, 3, 6, 4, 5, 7, 9};
int i = 0;
int j = array.lentgh - 1;
while (i < j){
    while(i
时间复杂度O(n)


一个数组中既有奇数也有偶数，奇数的下标是奇数，偶数的下标是偶数
int[] array = {1, 2, 3, 6, 4, 8, 7, 9};
int even = 0; //偶数
int odd = 1;  //奇数
int end = array.length - 1;
while(even <= end && odd <= end){
    if((array[end] & 1) == 0){ //如果数组最后一个是偶数
        swap(array, even, end);
        even+=2;
    }else{
        swap(array, odd, end);
        odd+=2;
    }
}
for(int i =0; i
时间复杂度O(n)


求一个有序数组中和等于8的下标
int[] array = {1, 2, 3, 4, 5, 6 ,7, 8};
int i = 0;
int j = array.length - 1;
while(i < j){
    if(array[i] + array[j] == 8){
        System.out.println("i="+i+" j="+j);
        i++;
        j--;
    }else if(array[i] + array[j] > 8){
        j--;
    }else{
        i++;
    }
}
时间复杂度O(n)


两个有序数组合并且去重合成新数组
int[] a = {4, 8, 10 ,28};
int[] b = {3, 9, 10, 17, 28, 30, 40};
int[] c = new int[a.length+b.length];
int i = 0; int j = 0; int k = 0;
while(i < a.length && j < b.length){
    if(a[i] < b[j]){
        c[k++] = a[i++];
    }else if(a[i] == b[j]){//去重
        c[k++] = a[i];
        i++;
        j++;
    }else{
        c[k++] = b[j++];
    }
}
while(i < a.length){
   c[k++] = a[i++];
}

while(j < b.length){
    c[k++] = b[j++];
}
for(int m = 0; m
时间复杂度O(n)


快速排序
int[] array = {3, 4, 1, 7, 6, 2, 0};
sortCore(array, 0, array.length -1);

private static void sortCore(int[] array, int startIndex, int endIndex) {
    if(startIndex > endIndex){
        return;
    }

    int boundray = boundray(array, startIndex, endIndex);

    sortCore(array, startIndex, boundray - 1);
    sortCore(array, boundray + 1, endIndex);
}

private static int boundray(int[] array, int startIndex, int endIndex) {
    int standard = array[startIndex];
    int leftIndex = startIndex;
    int rightIndex = endIndex;

    while(leftIndex < rightIndex){
        while(leftIndex < rightIndex && array[rightIndex] >= standard){
            rightIndex--;
        }
        array[leftIndex] = array[rightIndex];

        while(leftIndex < rightIndex && array[leftIndex] <= standard){
            leftIndex++;
        }
        array[rightIndex] = array[leftIndex];
    }
    array[leftIndex] = standard;
    return leftIndex;
}

GPU服务器私有云 webrtc一回声消除算法字符串最后一位加减算法数据结构算法算法字符串处理算法匹配算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71081.html

LeetCode 之 JavaScript 解答第344题 —— 反转字符串（Reverse Str

摘要：小鹿题目反转字符串编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组的形式给出。如果为奇数，当两个指针相等时，反转完毕。测试用例空字符串。奇数个数的字符串。长度为的字符串。考查内容对字符串的基本操作。 Time：2019/4/18Title: Reverse StringDifficulty: EasyAuthor: 小鹿题目：Reverse String(反转字...

bbbbbb 2019-08-23 17:03 评论0 收藏0
两数之和问题各变种多解法小结

摘要：两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处两数之和等于题目大意给出未排序数组和指定目标，返回数组中两数之和的组合元素下标要求下标从开始，而且，保证题目中有且只有个可行解解法暴力时间复杂度求解解题思路暴力二重循环求解两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwal...

lentoo 2019-08-16 10:34 评论0 收藏0
[Leetcode] 3Sum 4Sum 3Sum Closet 多数和

摘要：为了避免得到重复结果，我们不仅要跳过重复元素，而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数，然后再剩下的数中计算。 2Sum 在分析多数和之前，请先看Two Sum的详解 3Sum 请参阅：https://yanjia.me/zh/2019/01/... 双指针法复杂度时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题，...

trigkit4 2019-08-14 12:29 评论0 收藏0
[Leetcode] Remove Duplicates from Sorted Array 移除有

摘要：双指针法复杂度时间空间思路我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。代码双指针法复杂度时间空间思路思路和上题一样，区别在于记录前两个遍历到的数字来帮助我们判断是否出现了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...

kel 2019-08-14 12:30 评论0 收藏0
[LintCode/LeetCode] Trapping Rain Water [栈和双指针]

摘要：一种是利用去找同一层的两个边，不断累加寄存。双指针法的思想先找到左右两边的第一个峰值作为参照位，然后分别向后向前每一步增加该位与参照位在这一位的差值，加入，直到下一个峰值，再更新为新的参照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 评论0 收藏0