1. Paare in umgekehrter Reihenfolge in einem Array
(Lernvideo-Empfehlung:Java-Kurs)
[Thema]
Zwei Zahlen in einem Array, wenn die erste Zahl größer als die zweite Zahl ist Die beiden Zahlen bilden in umgekehrter Reihenfolge ein Zahlenpaar. Geben Sie ein Array ein und ermitteln Sie die Gesamtzahl der umgekehrten Paare im Array P. Und geben Sie das Ergebnis von P modulo 1000000007 aus. Das heißt, Ausgabe P%1000000007
Die Frage stellt sicher, dass das Eingabearray nicht die gleiche Nummer hat
Datenbereich:
对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
Code:
/** *在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。 * 输入一个数组，求出这个数组中的逆序对的总数 P。 * 并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007 * * 利用归并排序的思想(倒序) * 当得到left和right两个待归并的数组时，由于二者已经排好顺序 * 当left中的A元素大于right中的B元素， * 那么right.length-b_index 个逆序对 * */ int count; public int InversePairs(int [] array) { return Merge(array,0,array.length-1); } public int Merge(int[] a, int start, int end) { if (start >= end) return count; int i,j,mid,index; int[] temp; mid = (start + end) / 2; Merge(a,start,mid); Merge(a,mid+1,end); i = start; j = mid + 1; temp = new int[end-start+1]; index = 0; while (i<=mid && j<=end) { if (a[i] > a[j]) { count = (count +end - j + 1) % 1000000007; temp[index++] = a[i++]; } else { temp[index++] = a[j++]; } } while (i<=mid) temp[index++] = a[i++]; while (j<=end) temp[index++] = a[j++]; index = start; for (i=0;i
Nach dem Login kopieren
[Denken]
Wenn im Prozess der Zusammenführungssortierung Die Nummer des letzteren Arrays ist kleiner als Die Zahlen im vorherigen Array müssen in der Lage sein, Paare in umgekehrter Reihenfolge zu bilden, und die Anzahl der Paare in umgekehrter Reihenfolge kann berechnet werden Da die beiden zusammenzuführenden Arrays im Voraus zusammengeführt und sortiert wurden. Es wird nicht mehr oder weniger Statistiken geben als bisher.
Das Paar in umgekehrter Reihenfolge in [A, B] = das Paar in umgekehrter Reihenfolge in [A] + das Paar in umgekehrter Reihenfolge in [B] + das Paar in umgekehrter Reihenfolge, das A und B miteinander vermischt
Hinweis: Dort Eine besondere Anforderung in der Frage ist, dass Sie Modulo benötigen. Dieses Modulo moduliert nicht nur das Ergebnis, sondern muss auch in der Prozessberechnung modulo sein.
2. Zahlen, die nur einmal im Array erscheinen
[Titel]
Mit Ausnahme von zwei Zahlen in einem ganzzahligen Array erscheinen alle anderen Zahlen zweimal. Bitte schreiben Sie ein Programm, um diese beiden Zahlen zu finden, die nur einmal vorkommen.
【Code】
/** * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。 * 请写程序找出这两个只出现一次的数字。 * * 位运算中异或的性质： * 两个相同数字异或 = 0，一个数和 0 异或还是它本身。 * a ⊕ a = 0 * a ⊕ b ⊕ a = b. * a ⊕ 0 = a * * 当只有一个数出现一次时，我们把数组中所有的数，依次异或运算， * 最后剩下的就是落单的数，因为成对儿出现的都抵消了。 * * 当出现两个数只出现一次时，依旧是依次异或运算， * 剩下的结果是两个只出现一次的数的异或结果 * 因为这两个数不同，所以我们通过二进制的异或把二者分开，在依次异或即可分别得到 * */ public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int i,n,res,count,res1,res2; n = array.length; if (n == 0 || array == null) return; res = 0;// 记录两个不同的数的异或结果 for (i=0; i
Nach dem Login kopieren
【Denken】
Zuallererst: die Eigenschaften von XOR bei Bitoperationen: Zwei identische Zahlen sind XOR = 0, eine Zahl und 0 sind XOR oder sich selbst.
Wenn nur eine Zahl einmal vorkommt, XORen wir alle Zahlen im Array der Reihe nach und die letzte verbleibende Zahl ist die einzelne Zahl, da sich alle Zahlen, die paarweise erscheinen, aufheben.
Dieser Idee folgend schauen wir uns ein Array an, in dem zwei Zahlen (nehmen wir an, es sei AB) einmal vorkommen. Wir sollten zuerst XOR verwenden. Die verbleibende Zahl muss das Ergebnis der XOR-Verknüpfung von A und B sein. Die 1 in der Binärdatei dieses Ergebnisses repräsentiert die verschiedenen Bits von A und B. Wir nehmen die Ziffer der ersten 1, vorausgesetzt, es ist die 3. Ziffer, und teilen dann das ursprüngliche Array in zwei Gruppen auf. Das Gruppierungskriterium ist, ob die 3. Ziffer 1 ist. Auf diese Weise gehören die gleichen Zahlen definitiv zur gleichen Gruppe, da alle Ziffern der gleichen Zahlen gleich sind, während die unterschiedlichen Zahlen definitiv nicht zur gleichen Gruppe gehören. Dann XOR diese beiden Gruppen der Reihe nach gemäß der ursprünglichen Idee, und die verbleibenden beiden Ergebnisse sind diese beiden Zahlen, die nur einmal vorkommen.
(Empfehlungen für weitere verwandte Interviewfragen:Java-Interviewfragen und -antworten)
3. Zwei Zahlen, deren Summe S ist Zahlen so, dass ihre Summe genau S ist. Wenn es mehrere Zahlenpaare gibt, deren Summe gleich S ist, wird dasjenige mit dem kleinsten Produkt der beiden Zahlen ausgegeben.
Entsprechend jedem Testfall werden zwei Zahlen ausgegeben, wobei die kleinere zuerst ausgegeben wird.
【Code】
