算法之雙指針法(一)

Near_Li 發布于2019-08-16 11:12 / 932人閱讀

摘要：雙指針法在很多場景及算法中都有使用主要應用的算法題如下一個數組中有奇數也有偶數，將所有奇數放到數組左邊，將所有偶數放到數組右邊奇數偶數時間復雜度一個數組中既有奇數也有偶數，奇數的下標是奇數，偶數的下標是偶數偶數奇數如果數組最后一個是

   雙指針法在很多場景及算法中都有使用
   主要應用的算法題如下：

一個數組中有奇數也有偶數，將所有奇數放到數組左邊，將所有偶數放到數組右邊

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一回聲消除算法字符串最后一位加減算法數據結構算法算法字符串處理算法匹配算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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