首頁 後端開發 php教程 求 K 尺寸子陣列的功效 I

求 K 尺寸子陣列的功效 I

Nov 25, 2024 am 12:58 AM

Find the Power of K-Size Subarrays I

3254。求 K 尺寸子陣列 I

的威力

難度:

主題:陣列、滑動視窗

給定一個長度為 n 的整數 nums 陣列和一個 整數 k。

陣列的定義為:

  • 如果其所有元素都是連續並且按升序順序排序,則其最大元素。
  • 否則-1。

您需要找到大小為 k 的數字的所有子數組1

傳回大小為 n - k 1 的整數陣列結果,其中 results[i] 是 nums[i..(i k - 1)] 的

範例1:

  • 輸入: nums = [1,2,3,4,3,2,5], k = 3
  • 輸出: [3,4,-1,-1,-1]
  • 解釋: 有 5 個 nums 大小為 3 的子數組:
    • [1, 2, 3],最大元素為 3。
    • [2, 3, 4],最大元素為 4。
    • [3, 4, 3],其元素連續。
    • [4, 3, 2],其元素排序。
    • [3, 2, 5],其元素連續。

範例2:

  • 輸入: nums = [2,2,2,2,2], k = 4
  • 輸出: [-1,-1]

範例 3:

  • 輸入: nums = [3,2,3,2,3,2], k = 2
  • 輸出: [-1,3,-1,3,-1]

約束:

  • 1
  • 1 5
  • 1

提示:

  1. 我們可以使用帶有嵌套循環和 HashSet 的強力解決方案嗎?

解:

我們可以將任務分解如下:

問題分解:

  1. 給定一個長度為 n 的陣列 nums 和一個正整數 k。我們需要考慮大小為 k 的所有子數組併計算它們的 .
  2. 子數組的為:
    • 如果所有元素都是連續並且按升序順序排序,則子數組的最大元素。
    • 否則-1。
  3. 我們需要傳回一個大小為 n - k 1 的數組,其中每個元素對應於對應子數組的冪。

計劃:

  1. 滑動視窗方法:我們將在陣列上滑動並檢查長度為 k 的每個子陣列。
  2. 檢查子數組是否已排序:我們需要檢查子數組是否有連續且按升序排序的元素。
  3. 傳回最大值或-1:如果子陣列有效,我們傳回最大元素。否則,返回-1。

步驟:

  1. 檢查子數組是否已排序
    • 具有連續元素的排序子數組應具有以下屬性:對於子數組中的每個 i,nums[i 1] - nums[i] == 1。
  2. 滑動視窗
    • 對於每個長度為k的子數組,檢查它是否已排序,如果有效則傳回最大元素,否則傳回-1。

讓我們用 PHP 實作這個解:3254。求 K 尺寸子陣列 I
的功效

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function resultsArray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(resultsArray([1, 2, 3, 4, 3, 2, 5], 3));  // Output: [3, 4, -1, -1, -1]
print_r(resultsArray([2, 2, 2, 2, 2], 4));  // Output: [-1, -1]
print_r(resultsArray([3, 2, 3, 2, 3, 2], 2));  // Output: [-1, 3, -1, 3, -1]
?>
登入後複製

解釋:

  • 滑動視窗:我們使用從 i = 0 到 i = n - k 的 for 迴圈來考慮大小為 k 的所有子陣列。對於每個子數組,我們使用 array_slice() 來提取子數組。
  • 排序檢查:對於每個子數組,我們透過迭代子數組並檢查每對連續元素是否相差 1 來檢查它是否按連續元素排序。
  • 結果:如果子數組有效,我們將子數組的最大值附加到結果中。否則,我們追加 -1。

時間複雜度:

  • 我們正在迭代 n - k 1 個子數組。
  • 對於每個子數組,我們檢查元素是否連續,這需要 O(k) 時間。
  • 因此,整體時間複雜度為 O((n - k 1) * k),簡化為 O(n * k)。

邊緣情況注意事項:

  • 如果 k = 1,則每個子數組都是平凡排序的(它只包含一個元素),而每個子數組的冪將是該元素本身。
  • 如果子數組不連續,則立即傳回-1。

範例輸出:

  1. 對於 nums = [1, 2, 3, 4, 3, 2, 5], k = 3,輸出為 [3, 4, -1, -1, -1]。
  2. 對於 nums = [2, 2, 2, 2, 2], k = 4,輸出為 [-1, -1]。
  3. 對於 nums = [3, 2, 3, 2, 3, 2], k = 2,輸出為 [-1, 3, -1, 3, -1]。

該解決方案應該能夠有效地解決問題限制。

聯絡連結

如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!

如果您想要更多類似的有用內容,請隨時關注我:

  • 領英
  • GitHub

  1. 子數組:子數組是數組中連續的非空元素序列。 ↩

以上是求 K 尺寸子陣列的功效 I的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1677
14
CakePHP 教程
1431
52
Laravel 教程
1334
25
PHP教程
1281
29
C# 教程
1257
24
說明PHP中的安全密碼散列(例如,password_hash,password_verify)。為什麼不使用MD5或SHA1? 說明PHP中的安全密碼散列(例如,password_hash,password_verify)。為什麼不使用MD5或SHA1? Apr 17, 2025 am 12:06 AM

在PHP中,應使用password_hash和password_verify函數實現安全的密碼哈希處理,不應使用MD5或SHA1。1)password_hash生成包含鹽值的哈希,增強安全性。 2)password_verify驗證密碼,通過比較哈希值確保安全。 3)MD5和SHA1易受攻擊且缺乏鹽值,不適合現代密碼安全。

PHP類型提示如何起作用,包括標量類型,返回類型,聯合類型和無效類型? PHP類型提示如何起作用,包括標量類型,返回類型,聯合類型和無效類型? Apr 17, 2025 am 12:25 AM

PHP類型提示提升代碼質量和可讀性。 1)標量類型提示:自PHP7.0起,允許在函數參數中指定基本數據類型,如int、float等。 2)返回類型提示:確保函數返回值類型的一致性。 3)聯合類型提示:自PHP8.0起,允許在函數參數或返回值中指定多個類型。 4)可空類型提示:允許包含null值,處理可能返回空值的函數。

PHP和Python:解釋了不同的範例 PHP和Python:解釋了不同的範例 Apr 18, 2025 am 12:26 AM

PHP主要是過程式編程,但也支持面向對象編程(OOP);Python支持多種範式,包括OOP、函數式和過程式編程。 PHP適合web開發,Python適用於多種應用,如數據分析和機器學習。

在PHP和Python之間進行選擇:指南 在PHP和Python之間進行選擇:指南 Apr 18, 2025 am 12:24 AM

PHP適合網頁開發和快速原型開發,Python適用於數據科學和機器學習。 1.PHP用於動態網頁開發,語法簡單,適合快速開發。 2.Python語法簡潔,適用於多領域,庫生態系統強大。

PHP和Python:深入了解他們的歷史 PHP和Python:深入了解他們的歷史 Apr 18, 2025 am 12:25 AM

PHP起源於1994年,由RasmusLerdorf開發,最初用於跟踪網站訪問者,逐漸演變為服務器端腳本語言,廣泛應用於網頁開發。 Python由GuidovanRossum於1980年代末開發,1991年首次發布,強調代碼可讀性和簡潔性,適用於科學計算、數據分析等領域。

為什麼要使用PHP?解釋的優點和好處 為什麼要使用PHP?解釋的優點和好處 Apr 16, 2025 am 12:16 AM

PHP的核心優勢包括易於學習、強大的web開發支持、豐富的庫和框架、高性能和可擴展性、跨平台兼容性以及成本效益高。 1)易於學習和使用,適合初學者;2)與web服務器集成好,支持多種數據庫;3)擁有如Laravel等強大框架;4)通過優化可實現高性能;5)支持多種操作系統;6)開源,降低開發成本。

PHP和框架:現代化語言 PHP和框架:現代化語言 Apr 18, 2025 am 12:14 AM

PHP在現代化進程中仍然重要,因為它支持大量網站和應用,並通過框架適應開發需求。 1.PHP7提升了性能並引入了新功能。 2.現代框架如Laravel、Symfony和CodeIgniter簡化開發,提高代碼質量。 3.性能優化和最佳實踐進一步提升應用效率。

PHP的影響:網絡開發及以後 PHP的影響:網絡開發及以後 Apr 18, 2025 am 12:10 AM

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

See all articles