32--數組中重復的數字

1. 問題描述

找出數組中重復的數字。

在一個長度為 n 的數組 nums 里的所有數字都在 0~n-1 的范圍內。數組中某些數字是重復的,但不知道有幾個數字重復了,也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。

示例 1:

輸入:[2, 3, 1, 0, 2, 5, 3]
輸出:2 或 3

2. 解題詳情

由于只需要找出數組中任意一個重復的數字,因此遍歷數組,遇到重復的數字即返回。為了判斷一個數字是否重復遇到,使用集合存儲已經遇到的數字,如果遇到的一個數字已經在集合中,則當前的數字是重復數字。

偽代碼如下:

1.初始化集合為空集合,重復的數字 repeat = -1;
2.遍歷數組中的每個元素:
3.將該元素加入集合中,判斷是否添加成功;
4.如果添加失敗,說明該元素已經在集合中,因此該元素是重復元素,將該元素的值賦給 repeat,并結束遍歷。

時間復雜度:O(n)O(n)。
遍歷數組一遍。使用哈希集合(HashSet),添加元素的時間復雜度為 O(1)O(1),故總的時間復雜度是 O(n)O(n)。
空間復雜度:O(n)O(n)。不重復的每個元素都可能存入集合,因此占用 O(n)O(n) 額外空間。

class Solution {public int findRepeatNumber(int[] nums) {Set<Integer> set = new HashSet<Integer>();int repeat = -1;for (int num : nums) {if (!set.add(num)) {repeat = num;break;}}return repeat;}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/451720.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/451720.shtml
英文地址,請注明出處:http://en.pswp.cn/news/451720.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

實習期間的一些思考整理(3)2018.4.12~4.13

青云訣游戲體驗日報-2018.4.12 今日關鍵點&#xff1a;核心玩法 青云訣的核心玩法是“戰斗”、“成長”、“探索”&#xff08;這三點也是RPG類型的要素&#xff09;&#xff0c;側重于成長。 我是這樣想的&#xff0c;要想找出核心玩法是什么&#xff0c;就要看哪些玩法沒了&a…

整理的最全 python常見面試題(基本必考)

訪問flyai.club&#xff0c;一鍵創建你的人工智能項目作者&#xff1a;大蛇王https://blog.csdn.net/t8116189520/article/details/801655891、大數據的文件讀取① 利用生成器generator②迭代器進行迭代遍歷&#xff1a;for line in file2、迭代器和生成器的區別1)迭代器是一個…

Nginx安裝手冊(摘自入云龍老師教案,親測可用)

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 Nginx安裝手冊 一、 nginx安裝環境 nginx是C語言開發&#xff0c;建議在linux上運行&#xff0c;本教程使用Centos6.5作為安裝環境。 …

33--二維數組中的查找

1.問題描述 在一個 n * m 的二維數組中&#xff0c;每一行都按照從左到右遞增的順序排序&#xff0c;每一列都按照從上到下遞增的順序排序。請完成一個函數&#xff0c;輸入這樣的一個二維數組和一個整數&#xff0c;判斷數組中是否含有該整數。 示例: 現有矩陣 matrix 如下&…

XML Schema是什么

XML Schema 本身也是一種XML構造&#xff0c;它用來描述[哪個元素&#xff0c;在什么時候出現]&#xff0c;[該元素具有什么樣的屬性]等等&#xff0c;也就是說&#xff0c;XML Schema是對XML的樹形構造加以描述說明的一種語言。原本&#xff0c;使用DTD對XML的樹形構造加以描述…

js之base64上傳圖片

首先要搭建好springmvc&#xff0c;詳見https://www.cnblogs.com/zzb-yp/p/9295397.html 整體思路&#xff1a;前端代碼包括顯示和傳參&#xff08;這里的參數主要就是圖片的base64字符串&#xff09;&#xff0c;顯示主體部分是type“file”類型的input組件和一個提交按鈕 …

一些常用軟件的網絡端口協議分類介紹

最近有朋友請教我有關實現校園局域網視頻功能軟件的編寫問題&#xff0c;涉及到端口有關的知識&#xff0c;自己查了一些資料&#xff0c;發現這篇文章總結得比較不錯&#xff0c;常用軟件涵蓋得比較豐富&#xff0c;很實用&#xff0c;需要用到的時候可以查閱。于是決定將這篇…

WPF 使用皮膚影響按鈕自定義

在WPF項目中使用了 Theme的皮膚后&#xff0c;發現自定義的按鈕全部都是 皮膚里面的樣式&#xff0c;如下圖&#xff1a; 要自定義樣式&#xff0c;只有不給按鈕使用皮膚樣式。 如果想給某一個控件使用樣式&#xff0c;在前端Xaml的控件中&#xff0c;設置一下屬性即可&#xf…

各種數據庫對應的jar包、驅動類名和URL格式

見&#xff1a;http://blog.csdn.net/xuguiyi100/article/details/7970379 maven/Java/web/bootstrapQQ群&#xff1a;566862629。希望更多人一起幫助我學習。 1.1. 各種數據庫對應的jar包 具體如下&#xff1a; 數據庫類型 對應的Jar文件 Oracle 8i classes12.zip 或…

34--替換空格

1.問題描述 請實現一個函數&#xff0c;把字符串 s 中的每個空格替換成"%20"。 示例 1&#xff1a; 輸入&#xff1a;s “We are happy.” 輸出&#xff1a;“We%20are%20happy.” 2.解題思路 由于每次替換從 1 個字符變成 3 個字符&#xff0c;使用字符數組可方…

HTML的xmlns的作用

作用&#xff1a;由于xml允許定義自己的標記&#xff0c;但你定義的標記和其他人定義的標記有可能相同&#xff0c;但表示不同的含義。當文檔交換或者共享的時候就容易產生錯誤。為避免這種錯誤產生&#xff0c;xml采用名字空間聲明&#xff0c;允許你通過一個網址來識別你的標…

樹鏈剖分 講解+模板+習題

今天我們來講一下樹鏈剖分 樹鏈剖分是什么&#xff1f; 樹鏈剖分是一種用來維護樹上路徑信息的在線方法&#xff0c;可以處理在線。 通常通過一種方法&#xff0c;將一棵樹剖分成若干條鏈&#xff0c;然后通過數據結構&#xff08;線段樹&#xff0c;BIT等&#xff09;去維護。…

navicat 批量插入 測試數據

1. 前言 遇到線上大sql執行較慢, 10s, 做優化改進時&#xff0c;首先想到的是在本地造出一個類似的庫環境&#xff0c;先本地實驗。 然后往表中創建大量數據... 2. 方案 利用mysql函數來插入大量數據 代碼 BEGIN#Routine body goes here... DECLARE id int; DECLARE driverid …

互聯網產品用戶體驗設計的三大定律

好友發過來一PPT&#xff0c;文件名是互聯網產品的體驗設計&#xff0c;認真看完&#xff0c;收獲頗多&#xff0c;其中印象最深刻的是用戶體驗可用性的三大定律&#xff0c;正好FasterSoft正在打造互聯網精品平臺iWorld&#xff0c;最需要的時候好東西就上門來了&#xff0c;這…

oracle 對應的JDBC驅動 版本

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 Oracle版本jdk版本推薦jar包備注Oracle 8iJDK 1.1.xclasses111.zip Oracle 8iJDK 1.1.xclasses12.zip Oracle 9iJDK 1.1.xclasses111.ja…

JSP特點

1.JSP文件必須在JSP服務器內運行。 2.JSP文件必須生成servlet才能執行。 3.JSP頁面的第一個訪問者速度慢&#xff0c;因為需要編譯生成Servlet。 4.JSP不需要專門的客戶端&#xff0c;也不需要java運行環境&#xff0c;因為JSP輸出到頁面是標準的HTML文件。

35--用兩個棧實現隊列

1.問題描述 用兩個棧實現一個隊列。隊列的聲明如下&#xff0c;請實現它的兩個函數 appendTail 和 deleteHead &#xff0c;分別完成在隊列尾部插入整數和在隊列頭部刪除整數的功能。(若隊列中沒有元素&#xff0c;deleteHead 操作返回 -1 ) 示例 1&#xff1a; 輸入&#xf…

如何open一個新tab頁面

打開新tab頁的兩種方式 1 a標簽 function openwin(url) {var a document.createElement("a");a.setAttribute("href", url);a.setAttribute("target", "_blank");a.setAttribute("id", "camnpr");document.body.…

Linux中打開文件管理器的命令

在Mac中&#xff0c;我們可以使用open命令&#xff0c;在終端打開指定目錄下的文件管理器&#xff0c;在Linux中&#xff0c;同樣可以使用類似的命令&#xff1a;nautilus。 轉載于:https://www.cnblogs.com/chaoguo1234/p/9446106.html

final類與方法

final類---不可被繼承。 final方法---不可被覆蓋。