java簡單實現(xiàn)數(shù)組中的逆序?qū)?/h1>
更新時間：2019年03月06日 08:17:12 作者：zz0129
這篇文章主要為大家詳細(xì)介紹了java簡單實現(xiàn)數(shù)組中的逆序?qū)?，具有一定的參考價值，感興趣的小伙伴們可以參考一下
題目描述：
在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007
解題思路：
一開始一頭霧水，后面想到了使用歸并排序的思想，其實有多少個逆序?qū)Γ褪菤w并排序的時候，后面的數(shù)要超越前面多少個，嗯，好像不是很好說，要不然直接看代碼吧。還要注意，題目當(dāng)中說要輸出取模的結(jié)果，這說明數(shù)據(jù)可能非常大，所以如果只是單純的在最后取模的話可能還是無法避免數(shù)據(jù)太大的影響，所以我們在每次更新count的時候就對其進(jìn)行取模運算。
剛好又練習(xí)了一遍歸并排序，記錄一下
public class Solution {
int count;
public int InversePairs(int [] array) {
count = 0;
if(array != null){
divPairs(array, 0, array.length-1);
}
return count%1000000007;
}
public void divPairs(int[] array, int start, int end){
if(start >= end)
return;
int mid = (start + end)>>1;
divPairs(array, start, mid);
divPairs(array, mid+1, end);
mergePairs(array, start, mid, end);
}
public void mergePairs(int[] array, int start, int mid, int end){
int i = start, j = mid+1, k = 0;
int[] temp = new int[end-start+1];
while(i <= mid && j <= end){
if(array[i] <= array[j]){
temp[k++] = array[i++];
}else{
temp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= end){
temp[k++] = array[j++];
}
for(int x = 0; x < temp.length; x++){
array[start+x] = temp[x];
}
}
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
-
Spring?IOC容器基于XML外部屬性文件的Bean管理
這篇文章主要為大家介紹了Spring?IOC容器Bean管理XML外部屬性文件，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪 2022-05-05
-
這篇文章主要為大家詳細(xì)介紹了Spring中的AOP操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助 2022-02-02
-
springboot集成開發(fā)實現(xiàn)商場秒殺功能
這篇文章主要介紹了springboot集成實現(xiàn)商品秒殺功能，秒殺系統(tǒng)業(yè)務(wù)流程，本文通過實例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下 2019-12-12
-
泛型是Java中的高級概念，也是構(gòu)建框架必備技能，比如各種集合類都是泛型實現(xiàn)的，今天詳細(xì)聊聊Java中的泛型概念，希望有所收獲 2021-07-07
-
Spring AOP 是代理模式的應(yīng)用，可以使用JDK提供的Proxy類或通過字節(jié)碼增強來實現(xiàn)。下面這篇文章主要給大家介紹了關(guān)于Spring之AOP代理的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下 2018-05-05
-
Java Springboot之Spring家族的技術(shù)體系
今天帶大家來學(xué)習(xí)Spring家族的技術(shù)體系,文中有非常詳細(xì)的圖文介紹及代碼示例,對正在學(xué)習(xí)java的小伙伴們很有幫助,需要的朋友可以參考下 2021-05-05
-
這篇文章主要介紹了Jmeter如何將每次測試的結(jié)果保存到文件中的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2023-03-03
-
在面向?qū)ο蟪淌皆O(shè)計方法中，封裝（英語：Encapsulation）是指一種將抽象性函式接口的實現(xiàn)細(xì)節(jié)部分包裝、隱藏起來的方法。封裝可以被認(rèn)為是一個保護(hù)屏障，防止該類的代碼和數(shù)據(jù)被外部類定義的代碼隨機訪問 2021-10-10
-
這篇文章主要介紹了Java 生成帶Logo和文字的二維碼的方法，幫助大家更好的理解和學(xué)習(xí)使用Java，感興趣的朋友可以了解下 2021-04-04
-
java如何實時動態(tài)獲取properties文件的內(nèi)容
這篇文章主要介紹了java如何實時動態(tài)獲取properties文件的內(nèi)容，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2021-09-09
最新評論
題目描述：
在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出P%1000000007
解題思路：
一開始一頭霧水，后面想到了使用歸并排序的思想，其實有多少個逆序?qū)Γ褪菤w并排序的時候，后面的數(shù)要超越前面多少個，嗯，好像不是很好說，要不然直接看代碼吧。還要注意，題目當(dāng)中說要輸出取模的結(jié)果，這說明數(shù)據(jù)可能非常大，所以如果只是單純的在最后取模的話可能還是無法避免數(shù)據(jù)太大的影響，所以我們在每次更新count的時候就對其進(jìn)行取模運算。
剛好又練習(xí)了一遍歸并排序，記錄一下
public class Solution {
int count;
public int InversePairs(int [] array) {
count = 0;
if(array != null){
divPairs(array, 0, array.length-1);
}
return count%1000000007;
}
public void divPairs(int[] array, int start, int end){
if(start >= end)
return;
int mid = (start + end)>>1;
divPairs(array, start, mid);
divPairs(array, mid+1, end);
mergePairs(array, start, mid, end);
}
public void mergePairs(int[] array, int start, int mid, int end){
int i = start, j = mid+1, k = 0;
int[] temp = new int[end-start+1];
while(i <= mid && j <= end){
if(array[i] <= array[j]){
temp[k++] = array[i++];
}else{
temp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= end){
temp[k++] = array[j++];
}
for(int x = 0; x < temp.length; x++){
array[start+x] = temp[x];
}
}
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
-
Spring?IOC容器基于XML外部屬性文件的Bean管理
這篇文章主要為大家介紹了Spring?IOC容器Bean管理XML外部屬性文件，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05 - 這篇文章主要為大家詳細(xì)介紹了Spring中的AOP操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
-
springboot集成開發(fā)實現(xiàn)商場秒殺功能
這篇文章主要介紹了springboot集成實現(xiàn)商品秒殺功能，秒殺系統(tǒng)業(yè)務(wù)流程，本文通過實例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值,需要的朋友可以參考下2019-12-12 - 泛型是Java中的高級概念，也是構(gòu)建框架必備技能，比如各種集合類都是泛型實現(xiàn)的，今天詳細(xì)聊聊Java中的泛型概念，希望有所收獲2021-07-07
- Spring AOP 是代理模式的應(yīng)用，可以使用JDK提供的Proxy類或通過字節(jié)碼增強來實現(xiàn)。下面這篇文章主要給大家介紹了關(guān)于Spring之AOP代理的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-05-05
-
Java Springboot之Spring家族的技術(shù)體系
今天帶大家來學(xué)習(xí)Spring家族的技術(shù)體系,文中有非常詳細(xì)的圖文介紹及代碼示例,對正在學(xué)習(xí)java的小伙伴們很有幫助,需要的朋友可以參考下2021-05-05 - 這篇文章主要介紹了Jmeter如何將每次測試的結(jié)果保存到文件中的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-03-03
- 在面向?qū)ο蟪淌皆O(shè)計方法中，封裝（英語：Encapsulation）是指一種將抽象性函式接口的實現(xiàn)細(xì)節(jié)部分包裝、隱藏起來的方法。封裝可以被認(rèn)為是一個保護(hù)屏障，防止該類的代碼和數(shù)據(jù)被外部類定義的代碼隨機訪問2021-10-10
- 這篇文章主要介紹了Java 生成帶Logo和文字的二維碼的方法，幫助大家更好的理解和學(xué)習(xí)使用Java，感興趣的朋友可以了解下2021-04-04
-
java如何實時動態(tài)獲取properties文件的內(nèi)容
這篇文章主要介紹了java如何實時動態(tài)獲取properties文件的內(nèi)容，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09