欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

LeetCode——977.有序數(shù)組的平方（C++）-創(chuàng)新互聯(lián)

問題描述：

給你一個按?非遞減順序?排序的整數(shù)數(shù)組nums，返回?每個數(shù)字的平方?組成的新數(shù)組，要求也按?非遞減順序?排序。

成都創(chuàng)新互聯(lián)公司專注于企業(yè)成都營銷網(wǎng)站建設(shè)、網(wǎng)站重做改版、福田網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、商城建設(shè)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為福田等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

算法分析：

暴力解法這里就不講解了，重點是雙指針法。

方法一 ：雙指針（一）

我們從題目可以知道，數(shù)組是按升序排列的，可以有以下三種情況：

  • 數(shù)組元素全都是非負數(shù)的情況下，平方之后的數(shù)據(jù)依然也是升序的；
  • 數(shù)組元素全都是負數(shù)的情況下，平方之后的數(shù)據(jù)則是降序的；
  • 數(shù)組元素有非負也有負數(shù)，平方之后的數(shù)據(jù)先減小后增大

這樣看來，我們可以先找到數(shù)組中負數(shù)和非負數(shù)的分界線，記為flag，分界線左邊為負數(shù)，非負數(shù)的右邊為非負數(shù)

由圖可知：

  • nums[0] ~ nums[flag] 全是負數(shù)
  • nums[flag+1] ~ nums[nums.size()-1] 全是非負數(shù)

當(dāng)將原數(shù)組的數(shù)據(jù)平方之后，nums[0] ~ nums[flag]是單調(diào)遞減的， nums[flag+1] ~ nums[nums.size()-1]是單調(diào)遞增的

具體實現(xiàn)：

  • 定義一個結(jié)果數(shù)組ans
  • 定義兩個指針 i 和 j 分別指向 flag 和 flag+1 的位置，即 i = flag，j = flag+1；
  • 每次比較nums[i]和nums[j]的大小，選擇小的數(shù)據(jù)添加到ans中
  • 如果 i< 0 或者 j =?nums.size()，則表示某一方移到了邊界，則將另一方還未遍歷的數(shù)據(jù)依次添加到ans中
class?Solution?{
public:
????vectorsortedSquares(vector&?nums)?{
????????int?n?=?nums.size();
????????int?flag=?-1;
????????//找到最后一個負數(shù)的位置
????????for?(int?i?=?0;?i?ans;
????????//i為最后一個數(shù)組的位置，j為第一個>=0的位置
????????int?i?=?flag,?j?=?flag+?1;
????????while?(i?>=?0?||?j?

復(fù)雜度分析：

時間復(fù)雜度：O(n)，其中 nn是數(shù)組nums 的長度。

空間復(fù)雜度：O(1)，除了存儲答案的數(shù)組以外，我們只需要維護常量空間。

方法二 ：雙指針(二）

數(shù)組其實是有序的， 只不過負數(shù)平方之后有可能會成為大數(shù)，從而變成了先遞減后遞增的數(shù)組。那么數(shù)組平方的大值就在數(shù)組的兩端，不是在最左邊就是最右邊，而不可能在中間。此時我們依然可以考慮雙指針法。

  • 定義 i 指向數(shù)組起始位置，定義 j 指向數(shù)組終止位置
  • 定義一個新數(shù)組ans，和nums數(shù)組一樣的大小，讓 k 指向 ans 數(shù)組的終止位置。
  • 如果nums[i] * nums[i]< nums[j] * nums[j] 那么ans[k--] = nums[j] * nums[j];
  • 如果nums[i] * nums[i] >= nums[j] * nums[j] 那么ans[k--] = nums[i] * nums[i];?
class?Solution?{
public:
????vectorsortedSquares(vector&?nums)?{
????????int?n?=?nums.size();
????????vectorans(n);
        int i = 0;//數(shù)組的起始位置
        int j = n - 1;//數(shù)組的終止位置
        int k = n - 1;//ans數(shù)組插入數(shù)據(jù)的位置
????????while(i<=j)
????????{
????????????if(nums[i]*nums[i]?>nums[j]*nums[j])
????????????{
????????????????ans[k]?=?nums[i]*nums[i];
????????????????i++;
????????????}
????????????else
????????????{
????????????????ans[k]?=?nums[j]*nums[j];
????????????????j--;
????????????}
????????????--k;
????????}
????????return?ans;
????}
};

復(fù)雜度分析：

時間復(fù)雜度：O(n)，其中 nn 是數(shù)組 nums 的長度。

空間復(fù)雜度：O(1)，除了存儲答案的數(shù)組以外，我們只需要維護常量空間。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

標題名稱：LeetCode——977.有序數(shù)組的平方（C++）-創(chuàng)新互聯(lián)
文章鏈接：http://www.chinadenli.net/article36/docopg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、網(wǎng)站營銷、微信小程序、移動網(wǎng)站建設(shè)、企業(yè)建站、手機網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)