大數(shù)據(jù)雙指針算法問題的解決思路是什么

這篇文章將為大家詳細講解有關大數(shù)據(jù)雙指針算法問題的解決思路是什么，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

算法中的雙指針使用，有時候會覺得很巧妙，解決了很多的問題，有必要歸納總結一下，首先雙指針也是個很寬泛的概念，它類似于遍歷中的 i 和 j 但是其區(qū)別是，兩個指針是同時移動的，即沒有貢獻復雜度從O(N) 到 O(N*N) ，所以被很多算法大佬所推崇，所以基于此歸納總結出雙指針的常見解法和套路。

1.題型歸納

這里將題型歸納為三種，分別如下：

• 快慢指針（前后按不同步調(diào)的兩個指針）

• 前后雙端指針（一個在首，一個在尾部，向中間靠攏）

• 固定間隔的指針（以i, i + k的間距的兩個指針）

前面講到，這三種指針都是遍歷一次數(shù)組即可完成，其時間復雜度低于或者等于O(N) ，空間復雜度是O(1) 因為就兩個指針存儲。

2.常見題型

2.1快慢指針

相當經(jīng)典的一道題：

• 判斷鏈表是否有環(huán)-

通過步調(diào)不一致的兩個指針，一前一后一起移動，直到指針重合了

https://leetcode.com/problems/linked-list-cycle/description，代碼片段如下：

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
          ListNode fast = head;
    while (slow != null && fast != null) {
                 ListNode n = fast.next;
     fast = n == null ? null : n.next;
     if (slow == fast) {
         return true;
     }
                 slow = slow.next;
    }
    return false;
    }

• 尋找重復復數(shù)，從數(shù)組中找出一個重復的整數(shù)：https://leetcode-cn.com/problems/find-the-duplicate-number/

代碼解決如下：

public int findDuplicate(int[] nums) {
        // 將其看成是一個循環(huán)的鏈表，快慢指針循環(huán)
        int index1 = 0;
        int index2 = 0;
        do
        {
            index1 = nums[index1];
            index2 = nums[index2];
            index2 = nums[index2];
            
        }while (nums[index1] != nums[index2]);
        index1 = 0;
// 找出在哪個位置為起始點，可證必定在圓圈起點相遇
        while(index1 != index2){
            index1 = nums[index1];
            index2 = nums[index2];
        }
        return index1;
    }

2.2 前后首尾端點指針

• 二分查找

二分查找是典型的前后指針的題型，代碼如下：

public static int binarySearch(int[] array, int targetElement) {
    int leftIndex = 0, rightIndex = array.length - 1, middleIndex = (leftIndex + rightIndex) / 2;
    
    while(leftIndex <= rightIndex) {
      int middleElement = array[middleIndex];
      if(targetElement < middleElement) {
        rightIndex = middleIndex - 1;
      }else if(targetElement > middleElement) {
        leftIndex = middleIndex + 1;
      }else {
        return middleIndex;
      }
      
      middleIndex = (leftIndex + rightIndex) / 2;
    }
    
    return -1;
  }

2.3 固定間隔的指針

• 求鏈表中點https://leetcode-cn.com/problems/middle-of-the-linked-list/

// 快指針q每次走2步，慢指針p每次走1步，當q走到末尾時p正好走到中間。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            q = q.next.next;
            p = p.next;
        }
        return p;
    }
}

• 求鏈表倒數(shù)第k個元素 https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

    // 快慢指針，先讓快指針走k步，然后兩個指針同步走，當快指針走到頭時，慢指針就是鏈表倒數(shù)第k個節(jié)點。

    public ListNode getKthFromEnd(ListNode head, int k) {
        
        ListNode frontNode = head, behindNode = head;
        while (frontNode != null && k > 0) {

            frontNode = frontNode.next;
            k--;
        }

        while (frontNode != null) {

            frontNode = frontNode.next;
            behindNode = behindNode.next;
        }

        return behindNode;
    }

3. 模板總結

看完三個代碼，是不是覺得很簡單，下面總結一下三種雙指針的代碼模板

// 1.快慢指針
l = 0
r = 0
while 沒有遍歷完
  if 一定條件
    l += 1
  r += 1
return 合適的值

//2. 左右端點指針
l = 0
r = n - 1
while l < r
  if 找到了
    return 找到的值
  if 一定條件1
    l += 1
  else if  一定條件2
    r -= 1
return 沒找到

//3. 固定間距指針
l = 0
r = k
while 沒有遍歷完
  自定義邏輯
  l += 1
  r += 1
return 合適的值

關于大數(shù)據(jù)雙指針算法問題的解決思路是什么就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。